Questions tagged [svd]
Singular Value Decomposition (SVD) is a decomposition (factorization) of rectangular real or complex matrix into the product of a unitary rotation matrix, a diagonal scaling matrix, and a second unitary rotation matrix.
85
questions
1
vote
0
answers
37
views
Understanding this code to truncate the SVD
In Brunton's and Kutz's data-driven science and engineering book, page $19$, is a description of one way to truncate the SVD of a given matrix
I want to understand what the code for the variable <...
- 111
1
vote
0
answers
62
views
SVD decomposition and the update problem of matrix differential equations
For a matrix $Y(t) \in \mathbb{R}^{m \times n}$, its rank-r approximation could be represented in a factorized SVD-like form.
$$
Y(t) = U(t) S(t) V^T(t),
$$
where $U^{T}U = I_m$, $V^{T}V = I_n$ and $S ...
- 141
0
votes
0
answers
97
views
Computing smallest singular value of a matrix with explicit error control?
[Also posted here: https://mathoverflow.net/q/464433/]
Many good algorithms are out there computing truncated SVD: https://mathoverflow.net/q/161252.
I am trying to implement some codes to find the ...
- 161
13
votes
8
answers
3k
views
Real-world applications of eigendecomposition?
Cross-posted on Math.SE
Are there real-world applications that call specifically for eigenvalues rather than singular values?
I often see eigendecomposition used as "poor-man's SVD"
For ...
- 2,735
1
vote
1
answer
100
views
accuracy problem for a null space calculation on a sparse rectangular matrix
I have been using the QR-based approach on this link to find the null space of rectangular matrices, and possibly sparse matrices, that emerge as a result of some coupling conditions of different ...
- 130
9
votes
1
answer
1k
views
Why is it that SVD routines on nearly square matrices run significantly faster than if the matrix was highly non square?
In Python / Matlab, if you run a routine for SVD on a significantly non-square matrix, X, such as X.shape = (2,15000) you will ...
- 203
1
vote
0
answers
72
views
Computation of SVD of well-conditioned matrix takes more time than ill-conditioned matrix [closed]
I'm testing libraries for numerical computing and time they take to calculate SVD. During testing I encountered an issue for which I don't have an answer.
I generated 2 matrices:
random tall matrix ...
- 11
4
votes
1
answer
1k
views
Why are all eigen solvers iterative?
I have small dense square matrices for which I would like to compute the inverse by singular value decomposition, or equivalently solve the eigenvalue problem.
While there are many direct methods for ...
- 2,375
6
votes
1
answer
1k
views
Why is matrix inversion unstable when svd is stable?
I've heard that matrix is inversion is unstable whereas the SVD is stable.
Now, if $A$ is an invertible matrix, then its SVD is
$$
A = USV^T
$$
Then wouldn't it's inverse just be
$$
A^{-1} = (USV^T)^{...
- 832
3
votes
1
answer
99
views
SVD testing non zero values
I was looking at the matlab function pinv.m for the compuation of the pseudoinverse. The code uses the singular values decomposition.
$$
A = U D V
$$
When looking for non-zero diagonal elements it ...
- 153
3
votes
2
answers
984
views
My Complex Matrix SVD is Correct according to rule A = USV' but Wrong according to Matlab or any linear algebra library
I am working on Singular Value Decomposition for complex matrices. I implemented One Sided Jacobi algorithm. It gives exactly the same result as the svd function in Matlab for the real matrices. ...
- 31
1
vote
0
answers
77
views
Generate polynomial basis through a sequence of SVD
I need help to understand how to use the result given by an algorithm for constructing an orthonormal polynomial basis over $L^{2}(X)$, where $X\subset\mathbb{R}^2$, with respect to the inner product $...
- 219
2
votes
0
answers
47
views
Solving linear system and obtaining operator norm
I need to solve a linear system of the form $(\mathrm{Id} + \mathbf{J})\mathbf{x} = \mathbf{b}$ for $\mathbf{x}$ and I also need to compute the operator norm of $\mathbf{J}$ (i.e. the largest singular ...
- 183
2
votes
2
answers
306
views
Calculate determinant of unitary matrices based on SVD implementation
I have a real square matrix $X$ which I need to perform a Singular Value Decomposition on. Now, performing the operation
$$
X = USV^T
$$
as $U$ and $V$ are orthogonal, we know that $\det(X)=\pm\det(S)$...
- 203
0
votes
2
answers
591
views
Given a symmetric matrix, is it ok to apply Cholesky decomposition to see if it has negative eigenvalues?
I intend to check the diagonal of L, where A = L'L, for negative elements. However, I don't know if Cholesky is meaningful in theoretical / computational sense if there are some negative eigenvalues.
- 103
11
votes
1
answer
8k
views
How to compute Singular value decomposition of a large matrix with Python
Language: Python3
Problem: I have a matrix Q of shape [51200 rows x 51200 cols] stored in a binary file, each of the element in this matrix has a data type of complex64. To load the data into memory I ...
- 111
1
vote
1
answer
300
views
Asymptotic complexity of fixed-rank SVD
According to the Wikipedia article on Singular Value Decomposition, the asymptotic complexity of computing the SVD of an arbitrary m×n matrix M with m>n by the popular Householder QR methods is O(...
- 131
1
vote
0
answers
57
views
updating the matrix Adjugate/Cofactor
I would like to calculate the Adjugate matrix of a given matrix $A$, and its updates in the diagonal:
$B=A-\lambda I$, where $I$ is the identity matrix, $\lambda$ is a scalar. To this end, I am using ...
- 111
0
votes
0
answers
68
views
Formula for overdetermined logical matrix pseudoinverse not requiring SVD?
In https://commons.wikimedia.org/wiki/File:YI_%3D_PI.png, you will find a formula-based solution for an overdetermined logical matrix pseudoinverse. This simple formula gives the same result as the ...
- 101
2
votes
1
answer
122
views
Rank of a double-precision augmented matrix
Let $A$ be a matrix with real entries, and let $A_+$ be $A$ augmented by a single column.
From linear algebra we know
\begin{equation}
\operatorname{rank}(A_+) = \operatorname{rank}(A) \hspace{10pt} ...
- 255
2
votes
0
answers
430
views
Computing Singular Value Decomposition of small ($4\times 4$) matrices
I need to compute the Singular Value Decomposition (SVD) of many $4 \times 4$ matrices. I'm looking for SVD algorithms specialized for small matrices. I've read that the ...
- 131
0
votes
0
answers
365
views
Explanation of Givens rotation in Jacobi Rotation SVD
I'm trying to implement Singular Value Decomposition (homework of sorts) via the Jacobi Rotation method (more info here, pages 11 and 12).
I am stuck at the bullet saying (sorry for the picture, but I'...
- 101
2
votes
1
answer
352
views
Scaling/Performance of Matlab's svds function (Lanczos bidiagonalization)
I have a simple Matlab script which aims to compute $k$ singular values of a matrix $A$. $A$ is a random dense square matrix of size $5000\times5000$, with 100 of its singular values constrained to ...
- 145
1
vote
1
answer
528
views
Implementation of sparse matrix SVD for GPU
I have a sparse matrix $W$ which is almost-squared ($N+1 \times N$) and I would like to know the eigenvalues of $A = W^T W$. $A$ is Hermitian so the eigenvalues are real-positive valued.
The usual ...
- 11
2
votes
1
answer
1k
views
Matlab - Fast Computation of Truncated SVD / PCA
I'm working with a Matlab codebase wherein I'm attempting to solve A*c = b by approximating the (square) matrix A with its ...
- 145
3
votes
1
answer
74
views
Singular vectors of s1 for tiny dense matrices
I have a function whose main bottleneck is finding a(ny) singular vector pair in the space of the largest singular value, along with the singular value itself. This is done a huge number of times. ...
- 241
0
votes
1
answer
94
views
Analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^T A z$, where $A=uu^T+vv^T$
Let $u$ and $v$ be column vectors of size $n \gg 1$ (not both zero), and consider the matrix $A:=uu^T+vv^T$
Question
What is an analytic formula for $\arg\max_{\|z\|_\infty \le 1}z^TAz=\arg\max_{\|z\...
- 175
4
votes
1
answer
392
views
Analytic formula for leading eigenvector of $uu^T + vv^T$?
Let $u$ and $v$ be nonzero column vectors of size $n$ and consider the $n \times n$ positive-definite matrix $A:=uu^T + vv^T$. In this post https://math.stackexchange.com/a/112201/168758, the ...
- 175
3
votes
1
answer
416
views
Whitening transformation does NOT return a unit covariance matrix
For this question, I am using the following Wiki definition of Matrix whitening:
Suppose $X$ is a random (column) vector with non-singular covariance matrix $\Sigma$ and mean 0. Then the ...
- 133
1
vote
0
answers
87
views
Stability of SVD, Eigendecompositions, and pseudoinverse procedures in modern LAPACK routines
I have proposed an optimisation algorithm which I claim has improved upon the previous algorithm in a number of ways.
One of these claims is that my proposed solution requires no explicit SVD and ...
- 203
8
votes
1
answer
272
views
Finding the $i$-th largest eigenvalue of a matrix
Given a large matrix $A$ with eigenvalues $\sigma_1\ge \sigma_2 \ge \dotsc $, I want to determine only a subset of these values, say $\sigma_5,\sigma_8$ and $\sigma_{19}$. Is there an algorithm that ...
- 183
3
votes
1
answer
2k
views
Golub-Kahan-Lanczos Bidiagonalization Procedure implementation doesn't produce bidiagonal matrix
I'm trying to implement the aforementioned procedure using this website as a reference. At the end of the page the algorithm is described as follows:
I think I've mapped the given algorithm to code ...
- 133
2
votes
0
answers
773
views
finding null space to a complex matrix
I need to solve the following equation:
$$
\begin{pmatrix}
\frac{\omega^2}{c^2}\varepsilon_x-\mu_z^{-1}k_y^2-\mu_y^{-1}k_z^2 & \mu_z^{-1}k_xk_y & \mu_y^{-1}k_xk_z\\
\mu_z^{-1}k_xk_y &\...
- 217
2
votes
1
answer
782
views
How we can use CUR decomposition in place of SVD decomposition?
I have understood how CUR and SVD works, but have not been able to understand the following.
How can we use CUR in place of the SVD decomposition?
Do the $C$ and $R$ matrices in the CUR follow the ...
4
votes
1
answer
792
views
Nystrom approximation of SVD for asymmetric matrices
Suppose I have a symmetric matrix $K$. Subdivide $K$ into pieces as
$$K=\begin{pmatrix} K_{11} & K_{12} \\ K_{21} & K_{22}\end{pmatrix},$$
where $K_{21}=K_{12}^\top$. Then, the Nystrom ...
- 1,423
1
vote
2
answers
306
views
Inverting big symmetric and singular matrices
In this post I found a very similar probem to the one I have, but not a satisfactory answer for my purposes.
I have a set of matrices $C_\ell$. They are exactly symmetric by construction. ...
- 129
4
votes
1
answer
1k
views
Poor SVD reconstruction of singular matrix
I am trying to calculate the singular value decomposition of this matrix using numpy.linalg.svd .
However, reconstructing the matrix from the SVD gives a poor ...
- 53
1
vote
0
answers
167
views
Best algorithm for inversion of matrix spanning many orders of magnitude [duplicate]
I have a very similar problem to the one described in Calculate inverse of dense matrix with entries of very different magnitude. The reason why I am opening a new question is because as far as I ...
- 129
10
votes
2
answers
1k
views
How much regularization to add to make SVD stable?
I've been using Intel MKL's SVD (dgesvd through SciPy) and noticed that results are are significantly different when I change precision between ...
- 2,735
1
vote
0
answers
618
views
Pseudoinverse of a large sparse matrix in r
This question was moved from Cross-Validated: https://stats.stackexchange.com/questions/274042/pseudoinverse-of-large-sparse-matrix-in-r
I am trying to calculate the pseudoinverse of a large sparse ...
- 111
6
votes
1
answer
7k
views
Block-matrix SVD and rank bounds
Assume, we have an $m\times n$ block matrix $M=\left[\begin{array}{c c}A&C\\B&D \end{array}\right]$, where
$A$ is an $m_1 \times n_1$ matrix of rank $k_A$.
$B$ is an $m_2 \times n_1$ matrix ...
- 8,712
2
votes
0
answers
222
views
Generalized eigenvalue with null space
Define $S\in\mathbb{R}^{n\times n}$ as
$$S:=H+Q^\top V^{-1} Q.$$
$H,V$ are positive semidefinite. Here, $H$, $Q$, and $V$ are large, dense matrices but they are structured: I can write code for ...
- 1,423
7
votes
1
answer
501
views
What is the fastest way to compute the sum of the singular values of a matrix?
Is there a faster way to compute the nuclear norm (trace norm, sum of singular values) of a matrix A than computing SVD(A) directly (or diagonalizing A^*A)?
I am particularly interested in the case ...
- 171
2
votes
0
answers
77
views
Under what circumstances does Elemental's distributed SVD not work? [closed]
I am playing around with Elemental's distributed singular value decomposition and am running into two particular issues.
Building the test at tests/lapack_like/SVD.cpp, and running with
...
- 21
6
votes
2
answers
322
views
Lanczos algorithms for Hermitian system with Toeplitz kernel
Basically, I am trying to compute the SVD of a large Hermitian matrix $H$ using Lanczos iteration, while $H$ consists if a Toeplitz kernel $K$, which should be able to help speed up the matrix-vector ...
- 593
2
votes
0
answers
63
views
Optimal ordering in Jacobi SVD algorithm
In Jacobi SVD algorithm as given here every pair of columns of the matrix is orthogonalized until convergence. I want to know that how does the order of selection of the pair of columns affect the ...
- 121
2
votes
1
answer
444
views
Condition Number of Rectangular Matrices
The 2-norm condition number can be easily extended to rectangular matrices. I'm wondering if the inequality for the product of matrices still holds in that case, i.e.,
$\operatorname{cond}(AB) \leq \...
- 572
1
vote
2
answers
309
views
Efficient methods to solve large dense singular least square problem (linear system)
I am trying to solve a singular linear least square problem:
$$minimize: \phantom{2} ||Ax-b||^2 \\
subject \phantom{2} to: \phantom{2} x \ge 0$$
Here $ A \in R^{n \times m} $, and $ n\lt m$. here m ...
- 133
2
votes
0
answers
33
views
Choosing suitable polynomial degree based on information in advection stencil
I'm working on a finite volume advection scheme for unstructured meshes which uses a multidimensional polynomial weighted least squares fit for interpolating from cell centres onto faces.
In 2D, the ...
- 222
1
vote
1
answer
901
views
Iterative Closest Point Algorithm
I am currently working on an iterative closest point algorithm (in C++, see here).
I understand the basic premise of an ICP algorithm. You have two point clouds (a target and a reference) and you ...
- 111