# Tagged Questions

**2**

votes

**0**answers

22 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

**1**answer

62 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 ...

**0**

votes

**1**answer

85 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

**2**answers

288 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

**1**answer

53 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 ...

**5**

votes

**1**answer

160 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

**1**answer

79 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 ...

**4**

votes

**0**answers

94 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

**1**answer

103 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

**0**answers

85 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.
...

**1**

vote

**2**answers

135 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 ...

**4**

votes

**1**answer

54 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

**0**answers

101 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}$}. ...

**7**

votes

**0**answers

115 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

**1**answer

131 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 ...

**0**

votes

**0**answers

76 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 ...

**1**

vote

**0**answers

44 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

**1**answer

299 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

**0**answers

133 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

**1**answer

123 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

**1**answer

424 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

**0**answers

217 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 ...

**0**

votes

**1**answer

159 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

**0**answers

124 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).
$$
...

**2**

votes

**2**answers

137 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

**1**answer

223 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., ...

**3**

votes

**0**answers

108 views

### Computing the norm of the columns of an implicitly defined matrix

I have an $n \times n$ matrix $M = \Sigma W$ where $\Sigma$ is diagonal and $W$ orthogonal. $W$ is implicitly defined, i.e. I can only perform matrix-vector products (but I also have access to $W^T$).
...

**3**

votes

**2**answers

1k views

### Interesting relationships between Cholesky decomposition and diagonalization

Let $\Sigma$ be a hermitian positive definite matrix and $L$ be it's Cholesky decomposition so that $LL^\ast=\Sigma$. Furthermore, let's diagonalize $\Sigma$ as $\Sigma = P\Lambda P^\ast$. $\Lambda$ ...

**1**

vote

**1**answer

1k views

### Low rank Matrix factorization

Hello,
I've a SPD matrix A; which needs to be factorized as ${A=SS^{T}}$. But, using Cholesky for this purpose is prohibitive in terms of computational cost. Moreover, matrix is Dense and has a slow ...

**2**

votes

**0**answers

160 views

### Could SVD be used to optimize the partial inner-products?

Suppose a set $N$ of $n$ distinct points in $m-$dimensional space is given in $X\in\mathbb{R}^{n\times m}$. Also, suppose a subset $L\subset N$, $|L|=l<m<n$, with
$m-$dimensional coordinates in ...

**7**

votes

**2**answers

333 views

### polynomials with minimal $L_\infty$ norm on multiple disjoint intervals

It is well-known that Chebyshev polynomials are the polynomials of minimal $L_\infty$ norm on [-1,1] with leading coefficient 1. But what if you want the minimal $L_\infty$ polynomial on two disjoint ...

**2**

votes

**0**answers

331 views

### How many iterations are required for the Lanczos algorithm to converge?

I am trying to find the n smallest eigenvalues and eigenvectors of a NxN SPD matrix using Lanczos method. What is the number of iterations usually required? I mean, does it scale as $O(N)$ or ...

**5**

votes

**2**answers

622 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 ...