Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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.

Filter by
Sorted by
Tagged with
1 vote
0 answers
57 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 ...
Owen Jun's user avatar
  • 141
0 votes
0 answers
92 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 ...
Ma Joad's user avatar
  • 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 ...
Yaroslav Bulatov's user avatar
1 vote
1 answer
88 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 ...
Umut Tabak's user avatar
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 ...
tisPrimeTime's user avatar
1 vote
0 answers
71 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 ...
Intech's user avatar
  • 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 ...
Aurelius's user avatar
  • 2,365
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)^{...
NNN's user avatar
  • 760
3 votes
1 answer
98 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 ...
pinpon's user avatar
  • 153
3 votes
2 answers
926 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. ...
Emir evcil's user avatar
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 $...
Raibyo's user avatar
  • 219
2 votes
0 answers
46 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 ...
5d41402abc4's user avatar
2 votes
2 answers
294 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)$...
cheetah's user avatar
  • 153
0 votes
2 answers
532 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.
James's user avatar
  • 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 ...
SAM's user avatar
  • 111
1 vote
1 answer
273 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(...
mana's user avatar
  • 131
1 vote
0 answers
54 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 ...
user2393987's user avatar
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 ...
Youvan's user avatar
  • 101
2 votes
1 answer
118 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} ...
Glenn Davis's user avatar
2 votes
0 answers
388 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 ...
mana's user avatar
  • 131
0 votes
0 answers
342 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'...
cyau's user avatar
  • 101
2 votes
1 answer
338 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 ...
davewy's user avatar
  • 145
1 vote
1 answer
520 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 ...
simone's user avatar
  • 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 ...
davewy's user avatar
  • 145
3 votes
1 answer
73 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. ...
Ian Hincks's user avatar
0 votes
1 answer
90 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\...
dohmatob's user avatar
  • 175
4 votes
1 answer
353 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 ...
dohmatob's user avatar
  • 175
3 votes
1 answer
402 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 ...
GRS's user avatar
  • 133
1 vote
0 answers
81 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 ...
tisPrimeTime's user avatar
8 votes
1 answer
258 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 ...
dexter04's user avatar
  • 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 ...
Chen Guevara's user avatar
2 votes
0 answers
758 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 &\...
Physicist's user avatar
  • 217
2 votes
1 answer
764 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 ...
Prathamesh Raut's user avatar
4 votes
1 answer
759 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 ...
Justin Solomon's user avatar
1 vote
2 answers
305 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. ...
johnhenry's user avatar
  • 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 ...
myseun's user avatar
  • 53
1 vote
0 answers
165 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 ...
johnhenry's user avatar
  • 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 ...
Yaroslav Bulatov's user avatar
1 vote
0 answers
606 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 ...
Paul's user avatar
  • 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 ...
Anton Menshov's user avatar
  • 8,672
2 votes
0 answers
211 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 ...
Justin Solomon's user avatar
7 votes
1 answer
465 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 ...
Brent's user avatar
  • 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 ...
AidanGG's user avatar
  • 21
6 votes
2 answers
318 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 ...
lorniper's user avatar
  • 593
2 votes
0 answers
62 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 ...
sv_jan5's user avatar
  • 121
2 votes
1 answer
411 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 \...
gpavanb's user avatar
  • 572
1 vote
2 answers
305 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 ...
JW Xing's user avatar
  • 133
2 votes
0 answers
32 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 ...
hertzsprung's user avatar
1 vote
1 answer
879 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 ...
Developer Paul's user avatar
4 votes
1 answer
479 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 ...
Dr Krishnakumar Gopalakrishnan's user avatar