Questions tagged [svd]

In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix, with many useful applications in signal processing and statistics.

Filter by
Sorted by
Tagged with
14
votes
3answers
4k views

How does the SVD solve the least squares problem?

How do I prove that the least-squares solution for $$\text{minimize} \quad \|Ax-b\|_2$$ is $A^{+} b$, where $A^{+}$ is the pseudoinverse of $A$?
4
votes
2answers
2k views

What forms does the Moore-Penrose inverse take under systems with full rank, full column rank, and full row rank?

The normal form $ (A'A)x = A'b$ gives a solution to the least square problem. When $A$ has full rank $x = (A'A)^{-1}A'b$ is the least square solution. How can we show that the moore-penrose solves ...
375
votes
4answers
193k views

What is the intuitive relationship between SVD and PCA?

Singular value decomposition (SVD) and principal component analysis (PCA) are two eigenvalue methods used to reduce a high-dimensional data set into fewer dimensions while retaining important ...
10
votes
3answers
5k views

Derivative (or differential) of symmetric square root of a matrix

Let A be a square, symmetric, positive-definite matrix. Let S be its symmetric square root found by a singular value decomposition. Let vech() be the half-vectorization operator. Is there a ...
6
votes
3answers
914 views

Understanding a derivation of the SVD

Here's an attempt to motivate the SVD. Let $A \in \mathbb R^{m \times n}$. It's natural to ask, in what direction does $A$ have the most "impact". In other words, for which unit vector $v$ is $\| A ...
9
votes
3answers
7k views

Calculating SVD by hand: resolving sign ambiguities in the range vectors.

When calculating the SVD of the matrix $$A = \begin{bmatrix}3&1&1\\-1&3&1\end{bmatrix}$$ I followed these steps $$A A^{T} = \begin{bmatrix}3&1&1\\-1&3&1\end{bmatrix} ...
7
votes
3answers
12k views

Proof of Eckart-Young-Mirsky theorem

Could someone please explain why in this Wiki page one says "we know that $\exists(k+1)$ dimension space $(v_1,v_2, \dots, v_n)$" ?
-2
votes
1answer
847 views

Singular value decomposition proof

I need help in the following question. I'm not sure how to even begin to answer this. What is a possible proof for the following question? If $A$ is an $m \times n$ matrix and $b$ is an $m$-vector, ...
35
votes
2answers
16k views

How unique are $U$ and $V$ in the Singular Value Decomposition?

According to Wikipedia: A common convention is to list the singular values in descending order. In this case, the diagonal matrix $\Sigma$ is uniquely determined by $M$ (though the matrices $U$ and ...
15
votes
2answers
2k views

Why the SVD is named so…

The SVD stands for Singular Value Decomposition. After decomposing a data matrix $\mathbf X$ using SVD, it results in three matrices, two matrices with the singular vectors $\mathbf U$ and $\mathbf V$,...
37
votes
2answers
38k views

Why does the spectral norm equal the largest singular value?

This may be a trivial question yet I was unable to find an answer: $$\left \| A \right \| _2=\sqrt{\lambda_{\text{max}}(A^{^*}A)}=\sigma_{\text{max}}(A)$$ where the spectral norm $\left \| A \right \...
2
votes
2answers
868 views

SVD and the columns — I did this wrong but it seems that it still works, why?

I want to decompose $A = \begin{pmatrix} 3 & 1 & 2 \\ -2 & 1 & 3 \end{pmatrix}$ using the SVD. So $A = U \Sigma V^\star$. Now, I calculated the matrices $U$,$\Sigma$ which are $\...
1
vote
1answer
371 views

Low-rank Approximation with SVD on a Kernel Matrix

I have very little experience in linear algebra so please bear with me. Here's a little background of my issue. I'm working on a problem that utilizes a large kernel matrix, K. This matrix, when ...
56
votes
2answers
19k views

What do eigenvalues have to do with pictures?

I am trying to write a program that will perform OCR on a mobile phone, and I recently encountered this article : Can someone explain this to me ?
19
votes
4answers
24k views

Why does SVD provide the least squares and least norm solution to $ A x = b $?

I am studying the Singular Value Decomposition and its properties. It is widely used in order to solve equations of the form $Ax=b$. I have seen the following: When we have the equation system $Ax=b$, ...
4
votes
2answers
30k views

How to compute the SVD of a symmetric matrix?

If I have only the upper triangular part of a symmetric matrix $A$, how could I compute the SVD? $$\begin{pmatrix} 1 & 22 & 13 & 14 \\ & 1 & 45 & 24 \\ & & 1 & ...
6
votes
2answers
3k views

Singular vector of random Gaussian matrix

Suppose $\Omega$ is a Gaussian matrix with entries distributed i.i.d. according to normal distribution $\mathcal{N}(0,1)$. Let $U \Sigma V^{\mathsf T}$ be its singular value decomposition. What would ...
120
votes
7answers
54k views

Intuitively, what is the difference between Eigendecomposition and Singular Value Decomposition?

I'm trying to intuitively understand the difference between SVD and eigendecomposition. From my understanding, eigendecomposition seeks to describe a linear transformation as a sequence of three ...
127
votes
6answers
128k views

What is the difference between “singular value” and “eigenvalue”?

I am trying to prove some statements about singular value decomposition, but I am not sure what the difference between singular value and eigenvalue is. Is "singular value" just another name for ...
4
votes
1answer
6k views

Singular Value Decomposition of Rank 1 matrix

I am trying to understand singular value decomposition. I get the general definition and how to solve for the singular values of form the SVD of a given matrix however, I came across the following ...
11
votes
2answers
4k views

Find the maximum of $\operatorname{Tr}(RZ)$ over all orthogonal matrices $R$

Say I have the following maximization. $$ \max_{R: R^T R=I_n} \operatorname{Tr}(RZ),$$ where $R$ is an $n\times n$ orthogonal transformational, and the SVD of $Z$ is written as $Z = USV^T$. I'm ...
2
votes
1answer
323 views

How to apply SVD to real data to reduce the number of parameters?

I have a question about applying the Singular Value Decomposition (SVD) to real data. Say I have the equation $$ y= Ax+v$$ where $A \in \mathbb{R}^{m \times n}$, $y \in \mathbb{R}^m$, $x \in \mathbb{...
7
votes
3answers
8k views

Why do positive definite symmetric matrices have the same singular values as eigenvalues?

I realize that this is because when the eigenvalues are either 0 or 1 they will have the same square root. But why does this happen?
6
votes
3answers
2k views

What is the best way to compute the pseudoinverse of a matrix?

Mathematica gives the pseudo-inverse of a matrix almost instantaneously, so I suspect it is calculating the pseudo-inverse of a matrix not by doing singular value decomposition. Since the pseudo-...
5
votes
2answers
195 views

Gradient of $A \mapsto \sigma_i (A)$

Let $ A $ be an $m \times n$ matrix of rank $ k \le \min(m,n) $. Then we decompose $ A = USV^T $, where: $U$ is $m \times k$ is a semi-orthogonal matrix. $S$ is $k \times k$ diagonal matrix , of ...
36
votes
6answers
31k views

How can you explain the Singular Value Decomposition to Non-specialists?

I am giving a presentation in two days about a search engine I have been making the past summer, and my research involved the use of singular value decompositions, or in other words, $A=U\Sigma V^T$. ...
36
votes
1answer
13k views

Relationship between eigendecomposition and singular value decomposition

Let $A \in \mathbb{R}^{n\times n}$ be a real symmetric matrix. Please help me clear up some confusion about the relationship between the singular value decomposition of $A$ and the eigen-decomposition ...
21
votes
3answers
14k views

How is the null space related to singular value decomposition?

It is said that a matrix's null space can be derived from QR or SVD. I tried an example: $$A= \begin{bmatrix} 1&3\\ 1&2\\ 1&-1\\ 2&1\\ \end{bmatrix} $$ I'm convinced that QR (more ...
17
votes
2answers
6k views

Strang's proof of SVD and intuition behind matrices $U$ and $V$

In lecture 29 of MIT 18.06, Professor Gilbert Strang "proves" the singular value decomposition (SVD) by assuming that we can write $A = U\Sigma V^T$ and then deriving what $U$, $\Sigma$, and $V$ must ...
13
votes
4answers
5k views

Is $U=V$ in the SVD of a symmetric positive semidefinite matrix?

Consider the SVD of matrix $A$: $$A = U \Sigma V^\top$$ If $A$ is a symmetric, positive semidefinite real matrix, is there a guarantee that $U = V$? Second question (out of curiosity): what is the ...
6
votes
1answer
1k views

Continuity of an “SVD” operator

Let $A_n$ be a series of matrices, and let $A$ be another matrix. Let $S(B)$ be an SVD operator that takes a matrix and returns the left singular vectors matrix ordered by largest singular value to ...
5
votes
4answers
2k views

Matrix Linear Least Squares Problem with Diagonal Matrix Constraint

How could one solve the following least-squares problem with Frobenius Norm and diagonal matrix constraint? $$\hat{S} := \arg \min_{S} \left\| Y - XUSV^T \right\|_{F}^{2}$$ where the $S$ is a ...
4
votes
1answer
1k views

Finding Euler decomposition of a symplectic matrix

A symplectic matrix is a $2n\times2n$ matrix $S$ with real entries that satisfies the condition $$ S^T \Omega S = \Omega $$ where $\Omega$ is the symplectic form, typically chosen to be $\Omega=\left(...
2
votes
2answers
2k views

Number of Singular Values

Is there any equation which describes or estimates the number of singular values of a Matrix $X$ ? I found out that the number is equal to the number of eigenvalues of the Matrix $X^{*} X$, which are ...
1
vote
1answer
2k views

How to find the singular value decomposition of $A^TA$ & $(A^TA)^{-1}$

I want to find the singular value decomposition of $A^TA$ & $(A^TA)^{-1}$. The singular value decomposition of $A$ is $$A=U \Sigma V^T$$ Basically, I want to find the singular values of $A^TA$ &...
1
vote
2answers
867 views

2-norm of the orthogonal projection

So far, I've deduced that if the rank of A is n, then all the columns of A are linearly independent since A has n columns. As a result, m must be greater than or equal to n. In the case that m = n, ...
10
votes
2answers
5k views

Recovering eigenvectors from SVD

I am dealing with a problem similar to principal component analysis. Aka, I have a matrix and i want to recover the 'most efficient basis' to exaplin the matrix variability. With a square matrix these ...
0
votes
1answer
537 views

What constraints are needed to make singular value decomposition a unique transformation?

While the singular value decomposition of a matrix is very general, the standard factorization of a matrix A into two singular vector matrices U and V and a singular value matrix L is not unique, in ...
16
votes
8answers
18k views

Relation between Cholesky and SVD

When we have a symmetric matrix $A = LL^*$, we can obtain L using Cholesky decomposition of $A$ ($L^*$ is $L$ transposed). Can anyone tell me how we can get this same $L$ using SVD or Eigen ...
7
votes
1answer
3k views

Why SVD on $X$ is preferred to eigendecomposition of $XX^\top$ in PCA

In this post J.M. has mentioned that ... In fact, using the SVD to perform PCA makes much better sense numerically than forming the covariance matrix to begin with, since the formation of $XX^\top$ ...
15
votes
4answers
9k views

Why are singular values always non-negative?

I have read that the singular values of any matrix $A$ are non-negative (e.g. wikipedia). Is there a reason why? The first possible step to get the SVD of a matrix $A$ is to compute $A^{T}A$. Then ...
5
votes
2answers
3k views

Geometrical interpretations of SVD

I'm a bit confused by the various geometrical/visual interpretations of SVD or better I'm wondering how to reconcile them. Transformations : As explained here, the 3 matrices produced by the SVD can ...
5
votes
3answers
3k views

How to resolve the sign issue in a SVD problem?

Question: When performing a simple Singular Value Decomposition, how can I know that my sign choice for the eigenvectors of the left- and right-singular matrices will result in the correct matrix ...
5
votes
2answers
974 views

What is the proof that SVM can be used to solve the least squares problem with norm equality constraint?

I've seen it claimed that the solution to the minimization problem: $$\begin{align*} \arg \min_{b} \quad & {\left\| A b \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| b \right\|}_{2} ...
4
votes
2answers
818 views

Decompose a matrix into diagonal term and low-rank approximation

For a matrix $A$ the Singular Values Decomposition allows getting the closest low-rank approximation $$A_K=\sum_i^K\sigma_i \vec{v}_i \vec{u}_i^T$$ so that $\|A-A_k\|_F$ is minimal. I'd like to do ...
7
votes
1answer
906 views

SVD: proof of existence

I'm reading "Numerical Linear Algebra" by Lloyd Thefethen. For Singular Value Decomposition proof of existence it starts like this: "Set $\sigma_1=||A||_2$. By a compactness argument, there must be ...
3
votes
2answers
3k views

Change in singular values of matrix after left-multiply with a diagonal matrix

Say that we have an SVD for a matrix $X = U \Sigma V^T$, giving trace norm $||X||_{tr} = ||\Sigma||_{tr} = \sum \Sigma_{ii}$. I am wondering what happens to the SVD and/or trace norm if we left ...
3
votes
3answers
580 views

Minimum Least Squares Solution Using Pseudo Inverse (Derived from SVD) Is The Minimum Norm Solution - Extension from Vectors to Matrices

Given $A \in \mathbb{R}^{m \times n}$, $B \in \mathbb{R}^{k \times \ell}$, and $C\in \mathbb{R}^{m \times \ell}$. Show that for $X \in \mathbb{R}^{n \times k}$ $$ {A}^{\dagger} C {B}^{\dagger} = \arg \...
3
votes
1answer
133 views

$B - A \in S^n_{++}$ and $I - A^{1/2}B^{-1}A^{1/2} \in S^n_{++}$ equivalent?

Define $S^n_{++}$ to be the set that contains all the positive definite matrices. That is, if $A \in S^n_{++}$, then $A$ is a positive definite matrix. Now suppose that $A,B \in S^n_{++}$ are two ...
2
votes
1answer
66 views

Special Eigenvalues of a Matrix in Strang p.368

This question arises from Strang's Linear Algebra p.368. It concerns the matrix $$A = \left( \begin{array}{cccc} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & ...