{numerical-linear-algebra} questions involving algorithms for linear algebra computations.

learn more… | top users | synonyms

0
votes
1answer
124 views

Proving that the eigenvalues of a certain matrix product are positive

Let $A$ be an $m \times n$ matrix, and define: \begin{align*} U &= {\rm diag} \{ \frac{1}{\beta_j} \}, \beta_j = \sum_{k=1}^m |a_{kj}|, j = 1 \dots n \\ V &= {\rm diag} \{ \frac{1}{\alpha_i} ...
1
vote
0answers
149 views

open problems in Numerical Analysis [closed]

There are plenty of open problems in Graph Theory, Number Theory, and Combinatorics, according to the Open Problem Garden: http://www.openproblemgarden.org/. Yet there are no open problems in ...
2
votes
1answer
91 views

Matrix, singular values, Moore-Penrose-pseudoinverse

If A is any real mxn-matrix consider the block matrix $\begin{pmatrix} E&A^T \\ A&0\end{pmatrix}$. This matrix seems to have close connections with pseudo inverse, svd etc. which are probably ...
4
votes
1answer
70 views

Sensitivity of the range of a matrix

The distance between two subspaces $\mathcal{U}$ and $\widetilde{\mathcal{U}}$ is classically defined as $d(\mathcal{U},\tilde{\mathcal{U}}):=\|P-\tilde{P}\|$, where $P$ and $\tilde{P}$ are orthogonal ...
4
votes
2answers
89 views

Norm of triangular truncation operator on rank deficient matrices

Let $T_{n\times n}$ be a triangular truncation matrix, i.e. $$T_{i,j}=\begin{cases}1 & i\ge j\\ 0 & i<j \end{cases}$$ It is known that for arbitrary $A_{n\times n}$ $$\|T\circ ...
1
vote
1answer
92 views

Are there some algorithms to solve the diagonal matrix $X$ to the following matrix equation?

Suppose $X$ is an unknown $m \times m$ diagonal matrix. Given a scalar $0<c<1$, and a matrix $A$ of $m \times m$ size whose entries $0<A_{i,j}<1$. Are there some algorithms to find the ...
1
vote
1answer
154 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 ...
3
votes
4answers
215 views

Determinant of sum of Kronecker products

Given four real symmetric matrices $A,B \in \mathbb{R}^{n \times n}$ and $C,D \in \mathbb{R}^{m \times m}$, is there an efficient way to compute the determinant: $\det|A \otimes C + B \otimes D |$
0
votes
1answer
31 views

Large scale least squares of non symmetric and non square problems

Given a system like $b=Ax$ with an non symmetric and non square $A$ I would like to solve it having many elements in $x$ (lets say $10^7$). There is a large amount of algorithms for symmetric ...
1
vote
1answer
75 views

Decompositions of sparse symmetric matrices and methods for solving large linear equations

I am writing code for solving linear equations of the form $$A_{n\times n}\cdot x=1_n$$ where $n$ is on the order of $10^6$ and $A$ is a symmetric matrix with approx $10^3$ nonzero entries in each ...
4
votes
0answers
66 views

Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form: \begin{equation} A = \left[\begin{array}{c|c} ...
3
votes
2answers
111 views

QR-Decomposition of matrix valued function

Suppose I have a matrix valued function $$ F:\mathbb{R}\rightarrow\mathbb{R}^{m\times n},\qquad F(x)=\tilde Q\tilde R+xu_1v_1^T+xu_2v_2^T $$ where $\tilde Q\in\mathbb{R}^{m\times m}$ is orthogonal, ...
3
votes
1answer
98 views

submatrix of a given size with maximum frobenius norm

Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
-1
votes
1answer
80 views

Convergence for symmetric, positive semi-definite operator

Assume $u$ is a vector in the Euclidean space $\mathbb{R}^N$, $\|u\|=\sqrt{\langle u, u\rangle}$, where $\langle u, v\rangle = \sum_{i=1}^N u_i v_i$. I have that $\|u^{k+1}-u\|\leq \|I - c ...
0
votes
1answer
116 views

Perturbation of Cholesky decomposition for matrix inversion

I am looking for a computationally cheap way to compute $x$ such that $$(L L^T + \mu^2 I)x = y$$ where $L \in \mathbb{R}^{n \times n}$ is a lower triangular definite positive matrix (with some very ...
10
votes
2answers
325 views

Determinant and eigenvalues of a specific matrix

This came up in a conversation with an engineer friend of mine. Let $c>0$ be a constant. Let $A_{ij}$ be an $n$ by $n$ matrix with entries $$ A_{ij} = e^{-c(i-j)^2}. $$ Is there a name for this ...
1
vote
1answer
61 views

Augmenting orthonormal system into complete orthonormal system in a numerically stable way

Let us suppose we have a, say, 10 dimensional real space with 3 orthogonal unit vectors given. How do I complete this orthonormal system with 7 additional vectors into a complete ONS in a way that is ...
1
vote
0answers
58 views

How to solve a divergent linear system using iterative methods?

I have a matrix A which is symmetric and non-diagonal dominant. I tried to use Jacobi/Gauss-Seidel/SOR to solve it but it diverges. Is there any mechanism to condition the matrix for convergence using ...
2
votes
2answers
156 views

Probability for a random positive-semidefinite matrix to not be positive-definite?

If I take $A^TA$, where $A$ is a full-rank random matrix (let's say with Gaussian-distributed independent entries), can I expect it to be positive-definite? It will be positive semi-definite ...
5
votes
1answer
168 views

For a set of matrices $S$, find $X$ such that the elements of $SX$ commute

Let $S := \{A_0, A_1, \dots, A_d\}$, where $A_k \in \mathbb{C}^{n \times n}$, be a set of (generally noncommuting) matrices. I am interested in finding a nonsingular $X \in \mathbb{C}^{n \times n}$ ...
2
votes
1answer
85 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 ...
1
vote
2answers
189 views

Eigenvalue computation using inverse iteration

I have a positive definite matrix $A$. I need to compute the max eigen value of $A$ using inverse iteration. The problem is that there are duplicate maximum eigen values and so inverse iteration ...
2
votes
0answers
123 views

What would be a better method for numerical diagonalization of a certain Vandermonde-like matrix?

For the fractional iteration of the $\exp()$-function Hellmuth Kneser had 1942 proposed an analytic solution valid on the real numbers; there is a technical implementation for Pari/GP of this method ...
1
vote
0answers
118 views

The rationale of QR algorithm for computing eigenvectors

For a symmetric matrix $A$, the rationale for the success of applying QR to compute the spectral decomposition of $A = UDU^T$ is, for large $k$, the QR factorization of $A^k = Q_kR_k$ obeys, ...
7
votes
1answer
454 views

efficient rank-two updates of an eigenvalue decomposition (or more genearlly SVD)

Let $A$ be a symmetric matrix with eigenvalue decomposition $UDU^T$. Golub, et al. and Bunch, et al. have shown that given such an $A$, the eigenvalue decomposition of $A+\rho xx^t$ may be computed ...
4
votes
0answers
104 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 ...
0
votes
1answer
106 views

QR alogrithm for eigenvalue problem [closed]

Considering pure QR algorithm (without shifts and preliminary tridiagonal reduction) are there sufficient conditions for algorithm to converge to quasi-diagonal form? For the the following matrix $$ ...
5
votes
0answers
87 views

Inverses of the sums of all possible subsets of a set of symmetric and positive definite matrices

I have a set of $c$ matrices $A_1 ... A_c$ which are all symmetric and positive definite. I would like to calculate the inverses of all the possible sums, i.e. ...
3
votes
2answers
745 views

Sparse approximation of the inverse of a sparse matrix

Is it possible to approximate an inverse of a sparse matrix with a sparse matrix? The problem comes up in numerical non-linear quasi-Newton optimization: given a sparse Hessian a good starting point ...
1
vote
2answers
158 views

Alternative to Choleski Decomposition for Correlation Matrix

Let $\Sigma$ be a correlation matrix, ie. symmetric. The Choleski decompositon gives upper triangular $A$ such that $A^TA = \Sigma$. Instead of upper triangularity, we are looking for $A$ that is not ...
6
votes
1answer
341 views

The singular values of the Hilbert matrix

The $n\times n$ Hilbert matrix $H$ is defined as $H_{ij} = \frac{1}{i+j-1}, \qquad 1\leq i,j\leq n$ What is known about the singular values $\sigma_1\geq\ldots\geq \sigma_n$ of $H$? For example, ...
4
votes
1answer
56 views

Algorithm to quickly compute the individual inverses of a linear sequence of matrices

Fix $n \times n$ real symmetric positive definite matrices $A$ and $B$. Fix vectors $x$ and $y$ in $\mathbf{R}^n$. I want to compute the following bilinear products quickly: $\{x^T (A+mB)^{-1} ...
2
votes
0answers
116 views

Error bound on matrix vector multiplication

I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate. Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. ...
3
votes
1answer
72 views

Conjugate gradient algorithm where first search direction is not equal to residual

In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact ...
7
votes
0answers
123 views

Problems where Conjugate gradient works much better than GMRES

I am interested in cases where Conjugate gradient works much better than GMRES method. In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound ...
7
votes
1answer
137 views

Who first observed that Conjugate Gradient for Symmetric Positive Definite linear systems is a Krylov method?

Conjugate gradient was originally presented in the 50's before the modern understanding of Krylov subspaces (and the resulting iterative methods) was fully realized. As such, the method was derived ...
10
votes
0answers
146 views

What are the difficulties in proving almost-everywhere stability of Gaussian elimination?

It is well known that Gaussian elimination without pivoting is numerically unstable, and in practice Gaussian elimination is done with row pivoting (partial pivoting). A theorem of Wilkinson states ...
4
votes
1answer
118 views

standard practice for large dense truncated svd computations?

What are the standard methods of computing the rank-k truncated SVD of large dense matrices? My literature search yields results only for large sparse matrices. I assume for k small that you use a ...
2
votes
0answers
45 views

Most efficient algorithm for computing norm of the residual for the least squares problem in the rank deficient case

I have a large $m\times n$ data matrix $A$, $m>n$, and response $m$-vector $b$. I need to calculate $E = ||Ax-b||_2$ as quickly as possible, where $x$ is the least squares solution. I don't need ...
4
votes
1answer
314 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} ...
2
votes
0answers
136 views

Checking for error in conjugate gradient algorithm

What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction ...
0
votes
1answer
126 views

Nonlinear matrix equation 2

Solve the following nonlinear equations for $v$ and $w$ $Avv^TAw+Bvv^TBw=\lambda_1v+\lambda_2w$ $Aww^TAv+Bww^TBv=\lambda_1w+\lambda_2v$ $v^Tw=w^Tv=0$ $v^Tv=w^Tw=1$ where $\lambda_1, \lambda_2, ...
3
votes
1answer
525 views

Nonlinear matrix equation

Solve the following nonlinear equations for $v$ and $w$ $Avv^TAw=\lambda_1v+\lambda_2w$ $Aww^TAv=\lambda_1w+\lambda_2v$ $v^Tw=w^Tv=0$ $v^Tv=w^Tw=1$ where $\lambda_1, \lambda_2, \lambda_3$ are ...
2
votes
0answers
266 views

Quantifying the failure of the Cholesky factorization test for indefinite matrices

The Cholesky factorization is the classic test to check if a matrix is positive definite. In infinite precision it is also an exact test: A matrix has a Cholesky factorization iff it is positive ...
7
votes
2answers
1k views

Finding the smallest eigenvalues 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 $M$. $M$ is a Laplacian matrix, and it has the following structure: ...
0
votes
1answer
163 views

Ease of calculation of norm

I have SPD matrix A and two vectors z and b. Is there exist a norm where I can calculate $||A^{1/2}b-z||$ without having to calculate $A^{1/2}b$ explicitly ?
5
votes
0answers
125 views

reference for perturbation of projection result

Let $A$ and $B$ have the same rank and dimensions. If $P_A$ denotes the projection onto the range space of $A$, then $$ \|P_A - P_B\|_2 \leq \|A - B\| \cdot \min (\|A^\dagger\|_2, \|B^\dagger\|_2). $$ ...
0
votes
0answers
119 views

Finding peaks and determining noise

Hello , Im having one matrix which is product of two FFT transforms of one fits image ( astronomical image ). In that matrix you could find 3 peaks. One largest in center, and two around central ...
2
votes
2answers
140 views

Inflate a simplex, change rows to make the rank n

I have a simplex, n + 1 points in $\mathbb{R}^n$, which may have rank $r < n$. Is there a cheap way of "inflating" it to rank $n$, changing a few, all but $r$, of the points ? The points are ...
2
votes
1answer
249 views

A question for solutions of perturbed linear systems

Consider a linear system $$Ax=b\qquad (*)$$ and a sequence of perturbed linear systems $$(A+\delta A_n)x=b+\delta b_n. \qquad (n)$$ Suppose that all the linear systems are consistent (i.e., ...