All Questions
50 questions
15
votes
9
answers
9k
views
Exponential of large matrices
I want to make a diffusion kernel, which involves $e^{\beta A}$, where A is a large matrix (25k by 25k). It is an adjacency matrix, so it's symmetric and very sparse.
Does anyone have a ...
- 151
12
votes
5
answers
9k
views
Solving Lyapunov-like equation
The following matrix equation might be a Lyapunov-like equation, but it seems hard for me to develop a simpler way to solve it. From the computation effort, I need some help for solving the special ...
- 121
12
votes
2
answers
8k
views
Is there a way to simplify block Cholesky decomposition if you already have decomposed the submatrices along the leading diagonal?
Let's say we have a block matrix $ M =\left( \begin{array}{ccc}
A & B\\
B^{*} & C \end{array} \right)$ where $M$ is positive definite. ($A$ and $C$ are also positive definite.)
There is a ...
10
votes
4
answers
2k
views
How to solve Ax=b incrementally ?
Hi, everyone.
What I am struggling is the following problem. I have a linear matrix equation $Ax=b$, where $A$ is a known $n \times n$ large sparse real matrix, $x$ and $b$ are known $n \times 1$ ...
- 101
10
votes
1
answer
4k
views
Special considerations when using the Woodbury matrix identity numerically
Are there any special considerations when using the Woodbury matrix identity numerically? What is the best metric for numerical stability in this case? Can anyone point me to a good reference?
The ...
- 211
8
votes
1
answer
7k
views
Upper bound on largest eigenvalue of a real symmetric $n \times n$ matrix with all main diagonal entries positive, everywhere else nonpositive
Is there a good analytic upper bound on the largest eigenvalue of a real symmetric n*n matrix with all main diagonal entries strictly positive, all other entries <=0 with typically many of them ...
- 83
8
votes
2
answers
948
views
Best known bounds on (border) ranks of small matrix multiplication tensors?
The $(m,n,p)$-matrix multiplication tensor is a representation of the bilinear map $T\colon\mathbb{R}^{m\times n}\times\mathbb{R}^{n\times p}\rightarrow\mathbb{R}^{m\times p}$ given by $T(A,B)=AB$. ...
- 7,633
8
votes
1
answer
1k
views
Norm of inverse confluent Vandermonde matrix
Let $\{x_1,\dots,x_n\}$ be pairwise distinct complex numbers and $l_1+l_2+\dots+l_n=N$. The $N\times N$ confluent Vandermonde matrix is defined as
$$V=
\begin{bmatrix}
v_{1,0}&v_{2,0}&\dots&...
- 959
7
votes
2
answers
3k
views
Factorizing a block symmetric matrix
Let $X,Y\in\mathbb{R}^{n\times n}$ be symmetric matrices. You may assume that $X$ is positive semidefinite and $Y$ negative semidefinite, if needed, but not that they are invertible.
I would like to ...
- 20.2k
6
votes
3
answers
2k
views
Conjugate Gradient for a "slightly" singular system.
Suppose I have a symmetric $N \times N$ matrix A which has a one-dimensional Nullspace $N$. A is positive definite on $N^\bot$. In my case $N$ is the space of constant vectors (i.e. generated by ...
- 617
6
votes
2
answers
2k
views
Computation of a Drazin inverse
I need to compute the Drazin inverse $A^D$ of a singular M-matrix $A$, i.e., a matrix in the form $A=\lambda I -P$, where $P$ has nonnegative entries and $\lambda$ is the spectral radius (Perron value)...
- 20.2k
6
votes
1
answer
1k
views
Efficient computation of Markov chain transition probability matrix
Consider a continuous Markov chain $X = (X_t)$ on a finite state space and let $Q$ be the (given) transition rate matrix. This matrix is very sparse, with non-zero values on 3 diagonals only (so from ...
- 63
5
votes
2
answers
4k
views
sparsity of QR decomposition
Hi, everyone!
I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...
- 51
5
votes
1
answer
644
views
A conjecture about the submatrix of orthogonal matrix
Let $U$ be an $n\times n$ orthogonal matrix, i.e. $U\in\mathbb{R}^{n \times n}$. For any non-empty ordered sets $S_1,S_2\subset\{1,2,...,n\}$, define $U_{S_1S_2}$ to be an $|S_1|\times|S_2|$ submatrix ...
- 1,495
5
votes
0
answers
392
views
Preconditioner for finding the smallest eigenpairs of a large, but structured, matrix
I'm trying to find the eigenvector corresponding to the second smallest eigenvalue of a large $(4,000,000 \times 4,000,000)$ matrix $L$. $L$ is a graph Laplacian, with the following structure: $L = D -...
- 500
4
votes
1
answer
719
views
Singular value decomposition of truncated discrete Fourier transform matrix
Let $\mathbf{F}$ be a discrete Fourier transform (DFT) matrix such that
\begin{align}
F_{m,n}=e^{-j2\pi(m-1)(n-1)/N},\quad m,n=1,\ldots,N.
\end{align}
What we can say about the singular value ...
- 287
4
votes
1
answer
413
views
Lipschitz property of matrix function only depending on singular values
Let $f$ be a function from $\mathbb{R}^{n\times n}$ to $\mathbb{R}$ such that there exists another symmetric function $g$ (invariant under permutation of coordinates) from $\mathbb{R}^{n}$ to $\mathbb{...
- 1,495
4
votes
2
answers
948
views
Numerically solving for pseudo inverse of non-squared Vandermonde matrix
I have a linear system to solve, set up as:
$\bf{Ax}=\bf{b}$
with a non-squared matrix A,
$
\bf{A}=
\begin{bmatrix}
1 & A_{1} & A_{1}^2 & \cdots & A_{1}^n \\
1 & A_{2} & A_{...
- 41
4
votes
1
answer
1k
views
Matrix perturbation theory
I am having matrix $M_0$ with coresponding eigenvectors and 4 eigenvalues {0,0,a,-a}. Eigenvalue $\lambda=0$ is double degenerated. Now I am appliing small perturbation $\epsilon M_1$ and want to get ...
- 41
4
votes
1
answer
538
views
Rank 1 Approximation of Elementwise Inverse Matrix
I'm wondering whether there is a good way to solve the following optimisation problem.
Given a strictly positive quadratic matrix $A$, find two diagonal matrices $D_1$ and $D_2$ so that
$$ \| D_1 A ...
- 909
4
votes
0
answers
453
views
Convergence of the relaxation method for every parameter in the relevant disk
For large size matrices, the resolution of linear systems $Ax=b$ is often done iteratively. The matrix $A$ is split as $A=M-N$, with $M$ invertible, and one performs
$$x^{k+1}=M^{-1}(Nx^k+b).$$
The ...
- 52.3k
2
votes
1
answer
1k
views
On an eigenvalue inequality
Let $\lambda_1 (\cdot)$ be the larger absolute value
eigenvalue of a $2\times2$ matrix and $\lambda_2 (\cdot)$
the smaller absolute value eigenvalue of a $2\times2$ matrix, i.e.
$|\lambda_1 (\cdot)| \...
- 29
2
votes
1
answer
276
views
Possible pathological properties of positive definite matrix
Suppose $A$ is a positive definite matrix such that$$ I \preceq A \preceq 1.01I.$$ Is it possible that $\sum\limits_{i=1}^n A_{1i}$ can be arbitrarily large?
- 55
2
votes
1
answer
2k
views
How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) ("mathematicalized reformulation")
New edition of the question, "mathematicalized" (thanks to Gerhard).
Consider and integer valued n*n matrix M, with integers elements in the range -N < m < N.
I want to find integer-valued ...
- 24.8k
2
votes
3
answers
285
views
is there any efficient way to compute the follow matrix equations easily
Let $A$ and $D$ are $n\times n$ diagnal matrices, and $B$ is an $n\times n$ orthogonal matrix. Is there any efficient way to compute the follow matrix equations easily?
$\sum_{i=0}^{k} A^i \cdot B^T \...
- 21
2
votes
2
answers
606
views
Solving a matrix equation $X=c \cdot AXA' +I$ with a diagonal corrections
I am now struggling to solve the matrix $X \in R^{n \times n}$ in the following equation:
$X=c \cdot AXA' - diag(c \cdot AXA')+ I$,
where
(1) $A \in R^{n \times n}$ is a given matrix whose element ...
- 241
2
votes
1
answer
1k
views
Updating $LU$ decomposition after adding a sparse matrix
How many elements of $LU$ decomposition of a symmetric matrix change after adding a sparse symmetric matrix? Is it more efficient to recompute $LU$ decomposition after adding a sparse matrix comparing ...
- 2,205
2
votes
2
answers
599
views
Eigenvectors of a diagonalizable matrix
Suppose we have a n-by-n symmetric matrix K which can be factorized in a way, K = H * L * H', where L is a m-by-m diagonal matrix and H is a n-by-m matrix. In addition, let's assume n <= m.
Can we ...
- 21
2
votes
2
answers
402
views
Maximization of a matrix product by iterative methods
This might not be very difficult, but I think I may have gotten a little confused.
Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...
- 949
2
votes
1
answer
3k
views
Is it possible to decompose a symmetric, positive definite matrix in this way?
Let $\Sigma$ be a symmetric positive definite matrix. Then the Cholesky decomposition gives us $\Sigma=LL'$ where $L$ is lower triangular and unique.
Under what conditions (if any) does there exist ...
- 269
2
votes
0
answers
193
views
How to find moment condition for generalized method of moments?
Consider a scalar system with $2K$ outputs and $K+2$ unknowns:
$y_{k,1}=x_ka_1+n_{k,1} \quad y_{k,2}=x_ka_2+n_{k,1}$.
The variables $n_{k,\ell}$ are zero mean noise variables.
To estimate $a_1$ and $...
- 21
2
votes
0
answers
241
views
subspace separation and M-matrices
The separation between two square matrices $A$ and $B$, often used as a measure of the sensitivity of invariant subspace problems, is defined as
$$
\operatorname{sep}(A,B)=\min_{X\neq 0}\frac{\left\...
- 20.2k
1
vote
2
answers
262
views
How to approx. decompose a sym. p.d. matrix M into X'X?
M: pxp symmetric p.d. matrix with unit diagonals
n: number much smaller than p
Want a nonrandom nxp matrix X such that X'X is
close to M element-wise. If n gets larger, hopefully
difference ...
- 21
1
vote
1
answer
940
views
Uniqueness and invariance of the LDLT decomposition
A real symmetric positive semi-definite matrix $A$ can be decomposed in the form
$A = P^TLDL^TP$,
where $P$ is a permutation matrix, $L$ is a lower unit triangular matrix and $D$ is a diagonal ...
- 101
1
vote
2
answers
6k
views
Square root of non-positive definite matrix
Finding square root of matrices using Cholesky decomposition is limited to positive definite matrices. Any other method to find square root of matrix which has some diagonal values approximately zero (...
- 11
1
vote
1
answer
146
views
Norm of a matrix with clustered eigenvalues
On page 271 of Trefethen and Bau's Numerical Linear Algebra, it is constructed a matrix
$$A=2I_{m\times m}+0.5\cdot\frac{\text{rand}(m)}{\sqrt{m}}$$
for $m=200$, where rand(m) is an array with $m\...
- 13
1
vote
0
answers
95
views
Vandermonde-type factorization of moment matrix?
Consider $n,d \in \mathbb{N}_{>0}$, there are many functions $y:\mathbb{N}^{n} \to \mathbb{R}$. Now for simplicity, we denote $y(\alpha)$ to be $y_{\alpha}$. Let $|\alpha| = \sum_{i=1}^{n}\alpha_{i}...
- 275
1
vote
0
answers
77
views
Find a vector in the null space of a large dense matrix, where elements in the matrix are not directly accessible
I am working with Conjugate Gradient method to solve for 𝐴𝑥=𝑏, where 𝐴 is an extremely large PSD and Singular matrix. I cannot directly access the elements of 𝐴. The only thing I can do is ...
1
vote
0
answers
126
views
Fastest way to calculate the eigenvalues of a product of two Toeplitz matrices
I have the following problem:
I need to find the fastest way to calculate the eigenvalues of a matrix that is the product of two Toeplitz matrices. $B = A U$.
The first is a regular Toeplitz matrix $A$...
- 11
1
vote
0
answers
448
views
Smallest eigenvalue for large kernel matrix
I am interested in the the asymptotics of the minimum eigenvalue $\lambda_n^n$ of a class of kernel matrix $P = [ K(x_i - x_j) ]_{i,j}$, with $x_i$ equally spaced in the unit cube of $\mathbb{R}^d$.
...
- 151
1
vote
0
answers
174
views
Negative eigenvalue of Toeplitz Hermitian matrix?
I am working on estimation of a covariance matrix and I know that the matrix is Toeplitz. The desired matrix should not produce negative eigenvalues at all. However, sometime my estimation leads to a ...
- 495
1
vote
0
answers
98
views
LU growth factor applied to LDL of a Positive Semidefinite matrix [closed]
For a Positive Semidefinite matrix $A$, which we can decompose through $LDL$ decomposition as follows: $A=LDL^\text{T}$; how can we prove that for a decomposition $A=LU=L(DL^\text{T})$, the growth ...
- 111
1
vote
0
answers
1k
views
Covariance matrix formula interpretation - what am I missing?
I'm reading a paper that outlines the calculation of a covariance matrix like the following:
$C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$
What is the order of this matrix? My interpretation ...
- 111
0
votes
1
answer
540
views
Computing spectrum of convex combination of SPD matrices given individual spectral decompositions
Given the spectral decompositions of a non-commuting collection of symmetric positive definite $N\times N$ matrices $$\left\{ K_{i}\right\} _{i=1}^{M}, U_{i}D_{i}U_{i}^{T}=K_{i},\quad i=1,\dots,M,$$ ...
- 133
0
votes
1
answer
230
views
Solution of complex linear system
In Brubeck, Nakatsukasa, and Trefethen - Vandermonde with Arnoldi (example 3) they solve the following linear system:
$$\operatorname{Re}\left(\begin{array}{ccc}1 & \cdots & z_{1}^{n} \\ 1 &...
- 45
0
votes
2
answers
1k
views
The condition number of a scaled Vandermonde matrix
Let $V(x_1,..,x_n)$ be the Vandermonde matrix induced by $x_1,..,x_n$, and
let $\tilde{V} := V(\frac{x_1}{h},...,\frac{x_n}{h})$.
My intuition says that the condition number should be invariant under ...
- 265
0
votes
0
answers
32
views
Finding measure representation for rank 2 moment matrices
Assuming the following equation has a solution, I'm interested in finding any concrete values of $x_{1},\dots x_{n},y_{1},\dots y_{n},c_{1},c_{2},R$ that fulfills it.
$$
\begin{bmatrix}
1 & 1 \\
...
- 275
0
votes
0
answers
227
views
Decomposition of symmetric block matrix
I came across this question and got really interested about it. There, the OP asks whether is possible to decompose a $2n \times 2n$ block matrix:
$$ \begin{pmatrix}
X & I \\
I & Y
\end{...
0
votes
1
answer
266
views
Using QR or SVD to sum up finite number of matrices
Problem
I was wondering if there are any theoretical results that tackle the following problem:
Construct the following matrices $\mathbf{\mathcal{S}_{1}},\mathbf{\mathcal{S}_{2}},\ldots,\mathbf{\...
0
votes
0
answers
83
views
Bits of precision matrix reconstruction
We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$.
Suppose we have diagonalized using $LMR=D$.
I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of $\widetilde{...
- 13.9k