Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
16 votes
Accepted

Why is it that SVD routines on nearly square matrices run significantly faster than if the matrix was highly non square?

You are asking for a full (dense) SVD, which also needs to generate the unitary components of $U$ and $V$ which correspond with the null space of your input. for the $1000 \times 800$ case, your input ...
helloworld922's user avatar
13 votes

How much regularization to add to make SVD stable?

The singular value decomposition for a symmetric matrix $A=A^{T}$ is one and the same as its canonical eigendecomposition (i.e. with an orthonormal matrix-of-eigenvectors), while the same thing for a ...
Richard Zhang's user avatar
12 votes
Accepted

Real-world applications of eigendecomposition?

You can compute analytic functions of matrices using the eigendecomposition (or more generally by using the Jordan normal form in case the matrix is defective), you cannot do so with the singular ...
lightxbulb's user avatar
  • 2,162
11 votes
Accepted

Why is matrix inversion unstable when svd is stable?

The big issue is the condition number, which is defined as the ratio of the largest and smallest singular values. Suppose we expect: $$ S = \begin{bmatrix} 10^{-15}\\ &1 \end{bmatrix} $$ If we ...
helloworld922's user avatar
10 votes
Accepted

Why are all eigen solvers iterative?

There is simply no closed-form expression in terms of the four operations and radicals for the eigenvalues of a matrix greater than $4\times 4$. This follows from the facts that (1) there are ...
Federico Poloni's user avatar
9 votes

Robust algorithm for $2 \times 2$ SVD

I needed an algorithm that has little branching (hopefully CMOVs) no trigonometric function calls high numerical accuracy even with 32 bit floats We want to calculate $c_1, s_1, c_2, s_2, \sigma_1$ ...
petiaccja's user avatar
9 votes
Accepted

Poor SVD reconstruction of singular matrix

Algorithms for the SVD, as more or less every classical linear algebra algorithm based on orthogonal transformations, are normwise backward stable, i.e., it should be guaranteed that $\frac{\|USV^* - ...
Federico Poloni's user avatar
9 votes

Real-world applications of eigendecomposition?

In Quantum theory the observables corresponding to an operator are the eigenvalues of that operator. So, as an example, should you want the energy levels available to electrons in a molecule you need ...
Ian Bush's user avatar
  • 616
8 votes
Accepted

Block-matrix SVD and rank bounds

Let us begin with the exact singular value decompositions $A=U_{A}S_{A}V_{A}^{T}$, $B=U_{B}S_{B}V_{B}^{T}$, $C=U_{C}S_{C}V_{C}^{T}$, $D=U_{D}S_{D}V_{D}^{T}$. Then $$ M=\underbrace{\begin{bmatrix}U_{A} ...
Richard Zhang's user avatar
7 votes

Real-world applications of eigendecomposition?

The SVD is a special case of the eigen-decomposition, or could be thought closely related to it. For instance, the Kahan-Golub algorithm to compute the SVD is developed from the eigen-decomposition of ...
Lutz Lehmann's user avatar
  • 6,109
6 votes
Accepted

Finding the $i$-th largest eigenvalue of a matrix

No, there is nothing, as far as I know, unless you know approximately the location of these eigenvalues. As for methods that can compute a subset of the spectrum of a matrix, I know only of methods ...
Federico Poloni's user avatar
6 votes

Inverting big symmetric and singular matrices

Think of your matrix as block-diagonal with blocks $$ C_\ell = \begin{pmatrix} 0 & & \\ & D_\ell & \\ & & 0\end{pmatrix}. $$ Then it is clear that $$ C_\ell^{-1} = \begin{...
Wolfgang Bangerth's user avatar
6 votes
Accepted

Rank of a double-precision augmented matrix

Q1: No. Here's a counter-example: ...
Amit Hochman's user avatar
  • 1,081
6 votes
Accepted

Calculate determinant of unitary matrices based on SVD implementation

If you are prepared to go digging around in the fortran code: The SVD algorithm consists of a few parts: Bidiagonalization (usually using Householder reflectors) Use QR shifts to reduce the ...
Thijs Steel's user avatar
  • 1,723
6 votes

Real-world applications of eigendecomposition?

The eigenvalues of partial differential operators describing mechanical or electromagnetic systems are related to the resonance frequencies. For example, the frequencies at which a drum or guitar or ...
Wolfgang Bangerth's user avatar
6 votes

Real-world applications of eigendecomposition?

The energy levels available to a system (e.g. an atom, molecule, material, etc.) are the eigenvalues of the system's Hamiltonian matrix. The following diagram which is presented to grade 9 (typically ...
Nike Dattani's user avatar
5 votes
Accepted

Matlab - Fast Computation of Truncated SVD / PCA

Pseudoinverse can be computed using the SVD $A = USV^\top$ by: $$ A^+ = V\Sigma^+ U^\top $$ where $\Sigma^+$ is formed from $\Sigma$ by taking the reciprocal of all the non-zero elements. With that in ...
Tolga Birdal's user avatar
  • 2,229
5 votes

My Complex Matrix SVD is Correct according to rule A = USV' but Wrong according to Matlab or any linear algebra library

This should not be possible. $U$ and $V$ may be non-unique in the case where there are repeated singular values, but $s$ must be unique, since it is the sorted list of eigenvalues of $A^*A$ and ...
Federico Poloni's user avatar
5 votes

Real-world applications of eigendecomposition?

In seismology, decomposing the eigenvalues is used to calculate the fault plane (and auxillary fault plane as this is ambiguous) of an earthquake. As movement is assumed only on one plane and there is ...
RDavey's user avatar
  • 151
4 votes

Incremental SVD implementation in MATLAB

Here is a method that can handle column additions: http://pcc.byu.edu/resources.html. I updated it to handle row additions: ...
BBSysDyn's user avatar
  • 239
4 votes

Efficient methods to solve large dense singular least square problem (linear system)

Pretty sure that what you want is Non-negative least squares. Plenty of implementations already exist, so you shouldn't have to write any code to get going. https://en.wikipedia.org/wiki/Non-...
user1337732's user avatar
4 votes

Implementation of sparse matrix SVD for GPU

I'm no expert on software and certainly not on GPU software, but I can hopefully give some advice of a mathematical nature that might be helpful to you. Given a matrix $W$, one can embed $W$ in the ...
eepperly16's user avatar
4 votes
Accepted

Nystrom approximation of SVD for asymmetric matrices

Nemtsov, Averbuchm, and Schclar's "Matrix compression using the Nyström method" (2016) seems relevant: The Nyström method is routinely used for out-of-sample extension of kernel matrices. We ...
Richard's user avatar
  • 3,971
4 votes

Robust algorithm for $2 \times 2$ SVD

LAPACK has an implementation of the svd of a 2x2 triangular matrix. It appears to be very robust. The routine is XLASV2. To apply to a regular 2x2 matrix, you can simply apply a single givens rotation ...
Thijs Steel's user avatar
  • 1,723
4 votes

Asymptotic complexity of fixed-rank SVD

Yes. You can run rank-revealing QR on your matrix $A$, which will stop at step $k$ (hence effectively terminating in $O(mnk)$) and produce $A = QRP$, where $R$ has nonzeros only in its first $k$ rows, ...
Federico Poloni's user avatar
3 votes

Inverting big symmetric and singular matrices

You might be better served by either the LDL' decomposition or the Cholesky decomposition (in the event that C's are positive definite in addition to symmetric, they probably are). Though all of the ...
rchilton1980's user avatar
  • 4,896
3 votes
Accepted

Analytic formula for leading eigenvector of $uu^T + vv^T$?

One can start by writing the eigenvalue problem $$ \left(A - \lambda_i\,I\right) w_i = 0, \tag{1} $$ with $\lambda_i$ one of the two eigenvalues and $w_i$ its eigenvector. By using the definition of ...
fibonatic's user avatar
  • 450
3 votes
Accepted

Whitening transformation does NOT return a unit covariance matrix

As the comments notice, you may have some confusion in your head between covariance and sample covariance. However, that's not what causes your error. First of all, forget about getting the ...
Federico Poloni's user avatar
3 votes
Accepted

Golub-Kahan-Lanczos Bidiagonalization Procedure implementation doesn't produce bidiagonal matrix

This algorithm suffers from similar numerical stability problems as the symmetric Lanczos tridiagonalization algorithm, see here In exact arithmetic, after $k$ steps the following holds: $U_k^T U_k ...
wim's user avatar
  • 571

Only top scored, non community-wiki answers of a minimum length are eligible