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.
81
questions
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
68
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,355
6
votes
1
answer
998
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)^{...
- 668
3
votes
1
answer
95
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
0
votes
0
answers
22
views
Nimfa Lsnmf matrix factorization with sparse input: wrong/different result than dense input
I just started using Nimfa and working on a dummy example. I would like to do a matrix factorization (on a matrix for which we do not have all the entries) and I am assuming the following model (which ...
- 1
3
votes
2
answers
850
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
75
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
45
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
281
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)$...
- 153
0
votes
2
answers
407
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
6k
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
234
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
53
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 ...
- 11
0
votes
0
answers
66
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
107
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} ...
- 213
2
votes
0
answers
335
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
318
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
325
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
492
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
990
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
72
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
82
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\...
- 165
3
votes
1
answer
268
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 ...
- 165
3
votes
1
answer
374
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
75
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
231
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
1k
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
722
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 &\...
- 227
2
votes
1
answer
740
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
731
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,341
1
vote
2
answers
304
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
956
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
164
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,273
1
vote
0
answers
594
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,602
2
votes
0
answers
203
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,341
7
votes
1
answer
422
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
76
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
309
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
61
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
369
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
298
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 ...
- 123
2
votes
0
answers
30
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
833
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
4
votes
1
answer
478
views
Obtaining column vectors of pseudo-inverse of a matrix
I need to compute the pseudo-inverse of a very large rectangular dense matrix without any special structure or properties. I run out of memory/computing power and have no access to a large parallel ...
1
vote
1
answer
279
views
Compare reconstruction of matrices using SVD
I'm interested in how much 'signal' is retained from including k singular values in a Singular Value Decomposition, but I'm having trouble conceptualizing (or ...
- 2,119
1
vote
1
answer
769
views
On the fly/matrix free SVD of large sparse matrix
I am trying to apply SVD to large sparse matrices. I already compared the performances of Propack and irlba to those of the matlab svd and ...
- 13
3
votes
2
answers
2k
views
SVD of large block-hankel matrix
I am trying to do SVD of a large block-hankel matrix for model order reduction (Low rank approximation). However, I quickly run into memory issues in forming the large Block-Hankel matrix and CPU ...