Linear AlgebraThe Singular Value Decomposition2 of 6
The Singular Value Decomposition · 2
Computing the SVD from A Transpose A
We know that any matrix factors into a rotation or reflection, a stretch, and a second rotation or reflection as A=UΣVT, and now we need a way to find the matrices U,Σ, and V from the numbers in A.
1
Finding V and Σ from ATA
To build the SVD, we first want to find the perpendicular unit vectors vi in the input space and the singular values σi that tell us how much A stretches them. We cannot solve Avi=σiui directly like a normal eigenvalue problem because each equation contains two different unknown vectors, vi and ui, and A might not even be square. Taking a round trip through A and then AT brings vi back onto itself and gets ui out of the equation.
Finding V and Sigma from A Transpose A
While A sends each perpendicular input axis vi to σiui on the output ellipse, AT sends ui back to σivi, stretching vi by σi a second time:
(ATA)vi=λiσi2vi
No matter what shape A has, ATA is always square, symmetric, and positive semidefinite. Its eigenvalues λi are guaranteed to be real and never negative, so we take their square roots in decreasing order to get the singular values and divide the perpendicular eigenvectors of ATA by their lengths to get the unit columns of V:
σi=λi,λ1≥λ2≥…≥0
As v turns around the unit circle, the round-trip vector ATAv lines up with v only at the two perpendicular directions v1 and v2 where the output length ∥Av∥ reaches its maximum σ1 and minimum σ2. At those two directions, ATA scales v by σ12 and σ22.
Interactive c1
2
Computing the SVD of a Square Matrix
Once ATA gives us V and Σ, we still need the output directions ui to fill U. Let's find the full SVD A=UΣVT for a square matrix where every singular value is nonzero:
A=[3405]
Computing the SVD of a Square Matrix
A=[3405]=UΣVT
U,Σ,V=?
Text solution
Eigenvalues of ATAMultiply AT by A and solve det(ATA−λI)=0, listing the eigenvalues from largest to smallest:
Here VT and U both have determinant −1, so A reflects the input plane by VT, stretches the axes by 35 and 5, and reflects them onto u1 and u2 by U.
3
When a Singular Value Is Zero
The formula ui=σiAvi works whenever σi is nonzero, but it does not work if a singular value is zero because we cannot divide by zero. Here is a matrix with identical columns that squashes the entire 2D unit circle flat onto a 1D line:
A=[3434]
When a Singular Value Is Zero
Text solution
Eigenvalues of ATA and ΣSince ATA has trace 50 and determinant 0, its eigenvalues are 50 and 0, giving one positive singular value and one zero singular value:
Unit eigenvectors of ATA for VDivide the eigenvectors for λ1=50 and λ2=0 by their lengths to get unit vectors, noting that v2 is in the null space of A because Av2=[00]:
v1=21[11],v2=21[1−1]
Find u1 from σ1Av1Use σ1=52 to find the unit vector along the 1D output line:
Because σ2=0 multiplies u2 by zero in UΣVT, every output lands along u1, and either plus or minus u2 gives the exact same product A.
4
Computing the SVD of a Rectangular Matrix
What if A is not square, so the input and output spaces have different dimensions? For an m×n matrix A, the input matrix V is n×n, the output matrix U is m×m, and Σ has the same m×n shape as A.
For this 3×2 matrix, ATA is 2×2 and gives only two v vectors, while U needs three perpendicular columns in R3:
A=1111−11
Computing the SVD of a Rectangular Matrix
Text solution
Eigenvalues of ATA and the 3×2 matrix ΣCompute the 2×2 matrix ATA, put the square roots of its eigenvalues on the diagonal of Σ, and fill the extra bottom row with zeros:
Here u1 and u2 span the 2D plane of the output ellipse in R3, while u3 points perpendicular to that plane and gets multiplied by the bottom row of zeros in Σ.
When u1 and u2 have zeros in their entries, you can often see right away what u3 needs to be so the dot products are zero, or you can always solve the equations u1Tx=0 and u2Tx=0 (or run Gram-Schmidt). If A is wide instead of tall, such as 2×3, then ATA is 3×3 with at least one zero eigenvalue, which gives the third column v3 directly as an eigenvector in the null space of A.
As you move u3 around the 3D unit sphere, its projections onto u1 and u2 drop to zero only when u3 points straight out of the plane of the ellipse. That gives three perpendicular unit vectors to form the 3D coordinate system U.
A third unit vector completes a square 3D corner only when it points straight out of the ellipse's plane, at right angles to the first two.
5
The SVD and the Four Fundamental Subspaces
The vectors we found when σi=0 or when A was rectangular are not just extra columns to fill out the matrices. Splitting V and U right after the r nonzero singular values gives an orthonormal basis for each of the four fundamental subspaces of A.
The SVD and the Four Fundamental Subspaces
m×nAΣ=UΣVT=σ1⋱σr0⋱
rank(A)=?
Because the orthogonal matrices U and VT are rotations, possibly combined with a reflection, that keep every dimension intact, all the squashing in A=UΣVT happens inside Σ. If Σ has r nonzero singular values on its diagonal, then r dimensions survive:
rank(A)=r(σ1≥⋯≥σr>0)
V=
r
v1
⋯
vr
Row Space
C(AT)
n−r
vr+1
⋯
vn
Null Space
N(A)
U=
r
u1
⋯
ur
Column Space
C(A)
m−r
ur+1
⋯
um
Left Null Space
N(AT)
Splitting V and U after column r separates the directions that survive from the directions that get squashed to zero or missed by A:
VU=[row space C(AT)v1,…,vrnull space N(A)vr+1,…,vn],=[column space C(A)u1,…,urleft null space N(AT)ur+1,…,um]
For the rank-1 matrix A=[3434], moving the input x along the null space direction v2 does not change Ax at all, because A squashes v2 to zero. Only the part of x along the row space direction v1 survives: it gets stretched by σ1 along the column space direction u1, and never reaches the perpendicular left null space direction u2.
Only an input’s row-space component stays to get stretched along the column space, while its null-space component gets squashed to zero and nothing ever reaches the left null space.
Key concepts
To factor an m×n matrix into A=UΣVT, begin with the round-trip matrix ATA. Put its eigenvalues λ1≥λ2≥⋯≥0 in decreasing order: their square roots σi=λi go on the diagonal of the m×n matrix Σ (filled with zeros to match the shape of A), and the unit eigenvectors v1,…,vn fill the columns of the n×n matrix V.
How you find each column ui of the m×m matrix U depends on whether it has a nonzero singular value:
When σi>0, use ui=σiAvi
Compute ui=σiAvi, like u1=351Av1. Do not find ui by solving AAT separately when σi>0, because choosing eigenvector signs on their own can flip a sign so that Avi=−σiui.
When σi=0 or U needs more columns than V (m>n), use perpendicularity
You cannot use σiAvi (which either divides 0 by 0 or has no matching vi). Instead, pick unit vectors perpendicular to the u columns you already have, by swapping entries and flipping one sign in 2D (51[34]→51[−43]) or solving uiTx=0 in 3D.
Once U,Σ, and V are built, the number of nonzero singular values r is rank(A). Splitting V and U after column r gives you orthonormal bases for all four fundamental subspaces: v1,…,vr for the row space C(AT),vr+1,…,vn for the null space N(A),u1,…,ur for the column space C(A), and ur+1,…,um for the left null space N(AT).
6
Practice
1
For A=[122−2], the matrix ATA=[5−2−28] gives singular values σ1=3,σ2=2 and unit eigenvectors v1=51[1−2],v2=51[21]. A student solves AAT separately and picks u1=51[1−2] and u2=51[21]. Use ui=σiAvi to check whether these signs work and write the correct matrix U.
Because A is symmetric, AAT equals ATA, which makes it tempting to copy V directly into U=[51−525251]; that gives Av1=−σ1u1 because the student's u1 has the wrong sign.
Multiply A by v1 first: does Av1 point in the same direction as the student's u1, or the opposite direction?
(Warning: Because A is symmetric, AAT equals ATA, which makes it tempting to copy V directly into U=[51−525251]; that gives Av1=−σ1u1 because the student's u1 has the wrong sign.) The correct matrix is:
U=[−51525251]
2
Compute the full SVD A=UΣVT of the matrix A=[2−122].
Don't put the eigenvalues λ1=9,λ2=4 directly into Σ=[9004] without taking their square roots.
Start by computing ATA and listing its eigenvalues λ1,λ2 in decreasing order before finding the unit eigenvectors v1,v2.
Compute ATA and find its eigenvalues:
ATA=[22−12][2−122]=[5228]⟹λ1=9,λ2=4
Take square roots to get σ1=3 and σ2=2, so Σ=[3002]. (Warning: Don't put the eigenvalues λ1=9,λ2=4 directly into Σ=[9004] without taking their square roots.) The unit eigenvectors of ATA are:
Compute u1=5Av1=51[12], and swap entries with one sign flip to get a perpendicular unit vector u2=51[−21] (or its negative). Now transpose V to put together A=UΣVT (Warning: Leaving V untransposed puts v1 in the first column instead of the first row of VT, which multiplies out to [1224] instead of A):
Compute the full SVD A=UΣVT of the 3×2 matrix A=110011.
Compare the shapes of A,U,Σ, and VT first: how many columns does U need after you find u1 and u2 from v1 and v2?
The 2×2 matrix ATA is:
ATA=[2112]⟹λ1=3,λ2=1⟹σ1=3,σ2=1
Filling the extra bottom row of Σ with zeros to match the 3×2 shape of A gives Σ=300010. The unit eigenvectors of ATA are v1=21[11] and v2=21[1−1], so V=[212121−21]. Next, find u1 and u2 using ui=σiAvi (Warning: Remember to combine both 31 from σ1 and 21 from v1 into 61, rather than writing 21121 or 31121):
u1=3Av1=61121,u2=1Av2=2110−1
(Warning: Don't stop at two columns and leave U as 3×2; a full SVD needs a 3×3 orthogonal matrix U.) Solving u1Tx=0 and u2Tx=0 gives the third unit vector u3=311−11 (or its negative), so:
Find the full SVD A=UΣVT of the 2×3 matrix A=[200101], and use U,Σ, and V to state the rank of A and orthonormal bases for all four fundamental subspaces.
Since A is 2×3,ATA is 3×3 and gives three v vectors. Split the columns of V and U right after the last nonzero singular value.
Compute the 3×3 matrix ATA and find its eigenvalues:
ATA=400011011⟹λ1=4,λ2=2,λ3=0
Taking square roots gives σ1=2,σ2=2,σ3=0, and the 2×3 matrix Σ=[200200]. The unit eigenvectors of ATA are:
Multiplying v1 and v2 by A and dividing by σi gives u1=2Av1=[10] and u2=2Av2=[01], which already fills the 2×2 matrix U=[1001], so:
A=[1001][200200]10002121021−21
(Warning: Don't swap the roles of U and V or put v3 into the left null space. The vi vectors are in the input space R3 and split into the row space and null space, while the ui vectors are in the output space R2 and split into the column space and left null space.) Because there are r=2 nonzero singular values: