Exercises — Singular Value Decomposition (SVD) — full derivation

$U$ output space ${\mathbb{R}}^m={\mathbb{R}}^4$ par act karta hai, isliye $U$ is $4\times 4$. $V$ input space ${\mathbb{R}}^n={\mathbb{R}}^7$ par act karta hai, isliye $V$ is $7\times 7$. $\Sigma$ ko ${\mathbb{R}}^7\to {\mathbb{R}}^4$ map karna chahiye taaki product $U\Sigma V^{\top }$ is $4\times 7$ ho — isliye $\Sigma$ is $\boxed{4\times 7}$. Answer: $U$ is $4\times 4$, $\Sigma$ is $4\times 7$, $V$ is $7\times 7$.

Singular values ${\sigma }_i=\sqrt{{\lambda }_i}$ hote hain jahan ${\lambda }_i$, $A^{\top }A$ ke eigenvalues hain ($A$ ke khud ke eigenvalues nahi). $\sqrt{25}=5,\sqrt{9}=3,\sqrt{0}=0$. Ordered: ${\sigma }_1=5,{\sigma }_2=3,{\sigma }_3=0$. Rank $r$ = strictly positive singular values ki sankhya $=\boxed{2}$.

$A$ ka null space $\{x:Ax=0\}$ hai. Derivation se, $A{v}_i={\sigma }_i{u}_i$, isliye $A{v}_i=0$ tab hi hoga jab ${\sigma }_i=0$ ho. Yahan ${\sigma }_3={\sigma }_4=0$, isliye $\boxed{v_3,v_4}$ null space ko span karte hain.

Step A — $A^{\top }A$ banao (hamara safe gateway): $A^{\top }A=\left(\begin{array}{cc}3& 0\\ 0& -2\end{array}\right)\left(\begin{array}{cc}3& 0\\ 0& -2\end{array}\right)=\left(\begin{array}{cc}9& 0\\ 0& 4\end{array}\right).$ Step B — eigenvalues: pehle se diagonal hai, isliye ${\lambda }_1=9,{\lambda }_2=4$, jisse ${\sigma }_1=3,{\sigma }_2=2$ milta hai (sabse bada pehle). Step C — right singular vectors ($A^{\top }A$ ke eigenvectors): $v_1=(1,0{)}^{\top }$ ($\lambda =9$ ke liye), $v_2=(0,1{)}^{\top }$ ($\lambda =4$ ke liye). Isliye $V=I$. Step D — left singular vectors $u_i=\frac{1}{{\sigma }_i}A{v}_i$ ke zariye (ye sign lock karta hai): $u_1=\frac{1}{3}A(1,0{)}^{\top }=\frac{1}{3}(3,0{)}^{\top }=(1,0{)}^{\top }.$ $u_2=\frac{1}{2}A(0,1{)}^{\top }=\frac{1}{2}(0,-2{)}^{\top }=(0,-1{)}^{\top }.$ Isliye $U=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right),\Sigma =\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right),V=I.$ Check: $U\Sigma V^{\top }=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right)=\left(\begin{array}{cc}3& 0\\ 0& -2\end{array}\right)=A.$ ✓ Dhyaan do ki minus sign $U$ mein absorb ho gaya — singular values positive rehte hain.

$A^{\top }A=\left(\begin{array}{cc}4& 0\\ 0& 9\end{array}\right)$, eigenvalues $9,4$, isliye ${\sigma }_1=3,{\sigma }_2=2$. Sabse bada singular value $3$ hai, jo $2\text{nd}$ axis se match karta hai, isliye hume reorder karna hoga taaki $v_1$, $e_2$ ki direction mein point kare: $v_1=(0,1{)}^{\top },v_2=(1,0{)}^{\top }$, jisse $V=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ milta hai. $u_1=\frac{1}{3}A(0,1{)}^{\top }=\frac{1}{3}(0,3{)}^{\top }=(0,1{)}^{\top };u_2=\frac{1}{2}A(1,0{)}^{\top }=(1,0{)}^{\top }.$ $U=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\Sigma =\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right).$ Check: $U\Sigma V^{\top }=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}2& 0\\ 0& 3\end{array}\right)$. ✓

Yahan $m=1,n=2$. $A^{\top }A$ banao ($n\times n$ route $2\times 2$ hai): $A^{\top }A=\left(\begin{array}{c}3\\ 4\end{array}\right)\left(\begin{array}{cc}3& 4\end{array}\right)=\left(\begin{array}{cc}9& 12\\ 12& 16\end{array}\right).$ Eigenvalues solve karo: ${\lambda }^2-(9+16)\lambda +(9\cdot 16-12^2)=0\Rightarrow {\lambda }^2-25\lambda +0=0$, isliye $\lambda =25$ ya $0$. ${\sigma }_1=\sqrt{25}=5$, aur ${\sigma }_2=0$ (lekin $\Sigma$ is $1\times 2$, isliye usme sirf ek diagonal entry hai: $\Sigma =\left(\begin{array}{cc}5& 0\end{array}\right)$). Sanity check: ek single row ke liye, eklauta singular value us row ki length ke barabar hota hai: $\sqrt{3^2+4^2}=5$. ✓

Step A: $A^{\top }A=\left(\begin{array}{ccc}1& 2& 0\\ 2& 4& 0\end{array}\right)\left(\begin{array}{cc}1& 2\\ 2& 4\\ 0& 0\end{array}\right)=\left(\begin{array}{cc}5& 10\\ 10& 20\end{array}\right).$ Step B — eigenvalues: $\det (A^{\top }A-\lambda I)=(5-\lambda )(20-\lambda )-100={\lambda }^2-25\lambda =0$, isliye ${\lambda }_1=25,{\lambda }_2=0$. Isliye ${\sigma }_1=5,{\sigma }_2=0$, aur rank $r=1$ (rows/columns proportional hain). Step C — right singular vectors: ${\lambda }_1=25$: $(A^{\top }A-25I)v=0$ solve karo $\Rightarrow \left(\begin{array}{cc}-20& 10\\ 10& -5\end{array}\right)v=0\Rightarrow v_1\propto (1,2{)}^{\top }$, normalised $v_1=\frac{1}{\sqrt{5}}(1,2{)}^{\top }$. ${\lambda }_2=0$: $v_2\perp v_1$, isliye $v_2=\frac{1}{\sqrt{5}}(2,-1{)}^{\top }$. Step D — left singular vectors: $u_1=\frac{1}{5}A{v}_1=\frac{1}{5}\cdot \frac{1}{\sqrt{5}}A(1,2{)}^{\top }=\frac{1}{5\sqrt{5}}(5,10,0{)}^{\top }=\frac{1}{\sqrt{5}}(1,2,0{)}^{\top }.$ Check karo $\Vert u_1\Vert =\frac{1}{\sqrt{5}}\sqrt{1+4}=1$. ✓ $\{u_1\}$ ko ${\mathbb{R}}^3$ ke orthonormal basis tak extend karo (jaise Gram-Schmidt Process se): $u_2=\frac{1}{\sqrt{5}}(2,-1,0{)}^{\top },u_3=(0,0,1{)}^{\top }$. $U=\left(\begin{array}{ccc}\frac{1}{\sqrt{5}}& \frac{2}{\sqrt{5}}& 0\\ \frac{2}{\sqrt{5}}& -\frac{1}{\sqrt{5}}& 0\\ 0& 0& 1\end{array}\right),\Sigma =\left(\begin{array}{cc}5& 0\\ 0& 0\\ 0& 0\end{array}\right),V=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}1& 2\\ 2& -1\end{array}\right).$

Rank $r=1$ ke saath, singular vectors ko index $r$ par split karo (dekho Four Fundamental Subspaces):

• Column space ($\text{col}(A)\subset {\mathbb{R}}^3$) $=\text{span}\{u_1\}=\left\{\frac{1}{\sqrt{5}}(1,2,0{)}^{\top }\right\}$.
• Left null space ($\text{null}(A^{\top })$) $=\text{span}\{u_2,u_3\}=\left\{\frac{1}{\sqrt{5}}(2,-1,0{)}^{\top },(0,0,1{)}^{\top }\right\}$.
• Row space ($\text{col}(A^{\top })\subset {\mathbb{R}}^2$) $=\text{span}\{v_1\}=\left\{\frac{1}{\sqrt{5}}(1,2{)}^{\top }\right\}$.
• Null space ($\text{null}(A)$) $=\text{span}\{v_2\}=\left\{\frac{1}{\sqrt{5}}(2,-1{)}^{\top }\right\}$. Dhyaan do ki column space ⟂ left null space ${\mathbb{R}}^3$ mein, aur row space ⟂ null space ${\mathbb{R}}^2$ mein — SVD tumhe free mein orthogonal splitting de deta hai.

Direct squares ka sum: $1^2+2^2+2^2+4^2+0+0=1+4+4+16=25$. Singular-value side: ${\sigma }_1^2+{\sigma }_2^2=25+0=25$. Equal. ✓ Ye hamesha kyun hold karta hai: $U$ aur $V^{\top }$ rotations/reflections hain, jo kabhi lengths nahi badlate, isliye $A$ ka total squared "size" poori tarah $\Sigma$ mein, yani ${\sigma }_i^2$ mein store hota hai.

Eckart–Young theorem kehta hai ki best rank-$k$ approximation (Frobenius norm mein) $A_k={\sum }_{i=1}^k{\sigma }_i{u}_i{v}_i^{\top }$ hai. Yahan $k=1$: $A_1={\sigma }_1{u}_1{v}_1^{\top }=5\cdot \frac{1}{\sqrt{5}}\left(\begin{array}{c}1\\ 2\\ 0\end{array}\right)\cdot \frac{1}{\sqrt{5}}\left(\begin{array}{cc}1& 2\end{array}\right)=\frac{5}{5}\left(\begin{array}{c}1\\ 2\\ 0\end{array}\right)\left(\begin{array}{cc}1& 2\end{array}\right)=\left(\begin{array}{cc}1& 2\\ 2& 4\\ 0& 0\end{array}\right)=A.$ Exact kyun? $A$ pehle se rank $1$ hai (${\sigma }_2=0$), isliye uski rank-1 approximation kuch nahi khooti. Approximation error $\sqrt{{\sum }_{i>k}{\sigma }_i^2}=\sqrt{0}=0$ ke barabar hai.

$\Sigma =\left(\begin{array}{cc}5& 0\\ 0& 0\\ 0& 0\end{array}\right)$, $3\times 2$ hai. Nonzero entries invert karo aur $2\times 3$ mein transpose karo: ${\Sigma }^{+}=\left(\begin{array}{ccc}\frac{1}{5}& 0& 0\\ 0& 0& 0\end{array}\right).$ Phir $A^{+}=V{\Sigma }^{+}{U}^{\top }$. Multiply karo: $V{\Sigma }^{+}=\frac{1}{\sqrt{5}}\left(\begin{array}{cc}1& 2\\ 2& -1\end{array}\right)\left(\begin{array}{ccc}\frac{1}{5}& 0& 0\\ 0& 0& 0\end{array}\right)=\frac{1}{\sqrt{5}}\left(\begin{array}{ccc}\frac{1}{5}& 0& 0\\ \frac{2}{5}& 0& 0\end{array}\right).$ $U^{\top }$ ki pehli row $\frac{1}{\sqrt{5}}(1,2,0)$ hai. Multiply karne par: $A^{+}=\frac{1}{\sqrt{5}}\left(\begin{array}{ccc}\frac{1}{5}& 0& 0\\ \frac{2}{5}& 0& 0\end{array}\right)U^{\top }=\frac{1}{25}\left(\begin{array}{ccc}1& 2& 0\\ 2& 4& 0\end{array}\right).$ Check $A{A}^{+}A=A$: kyunki $A^{+}$ "jahan possible ho undo karo" wala map hai, $A$ apply karo, phir $A^{+}$, phir $A$ dobara karo to $A$ wapas milta hai. (Neeche checks mein numerically verify kiya gaya hai.)

Covariance-jaisi matrix $X^{\top }X$ hai (ek factor $\frac{1}{N-1}$ tak). Uske eigenvectors exactly $v_i$ hain — principal component directions. Uske eigenvalues ${\sigma }_i^2$ hain. Isliye:

• $v_i$ = $i$-wa principal axis (data mein $i$-wi sabse zyada spread ki direction).
• $\frac{{\sigma }_i^2}{N-1}$ = $v_i$ par project kiye gaye data ka variance.
• Pehle $k$ components se captured total variance ka fraction $\frac{{\sum }_{i\le k}{\sigma }_i^2}{{\sum }_i{\sigma }_i^2}$ hai. Isliye data matrix ka SVD hi PCA hai — koi covariance matrix explicitly banane ki zaroorat nahi (aur numerically nahi banana zyada safe bhi hai).

$A=U\Sigma V^{\top }$ se shuru karo. Dono sides transpose karo ($(XY{)}^{\top }=Y^{\top }{X}^{\top }$ aur $(\Sigma {)}^{\top }={\Sigma }^{\top }$ use karke): $A^{\top }=(U\Sigma V^{\top }{)}^{\top }=V{\Sigma }^{\top }{U}^{\top }.$ Ye $A^{\top }$ ka ek valid SVD hai: $V$ aur $U$ orthogonal hain, aur ${\Sigma }^{\top }$ woh (transposed-shape) diagonal matrix hai jo same diagonal entries ${\sigma }_i$ carry karta hai. Kyunki singular values matrix se uniquely determined hote hain, ${\Sigma }^{\top }$ ke nonzero diagonal entries — jo $\Sigma$ ke barabar hain — $A^{\top }$ ke singular values hain. Isliye $A$ aur $A^{\top }$ ke same nonzero singular values hain. $■$ (Left/right singular vectors ke roles simply swap ho jaate hain.)

Kisi bhi unit vector ko $v$-basis mein likho: $x={\sum }_i{c}_i{v}_i$ jahan ${\sum }_i{c}_i^2=1$ (kyunki $v_i$ orthonormal hain, $\Vert x{\Vert }^2=\sum c_i^2$). $A{v}_i={\sigma }_i{u}_i$ use karke $A$ apply karo: $Ax={\sum }_i{c}_i{\sigma }_i{u}_i.$ $u_i$ orthonormal hain, isliye $\Vert Ax{\Vert }^2={\sum }_i{c}_i^2{\sigma }_i^2.$ Kyunki ${\sigma }_1\ge {\sigma }_i$ har $i$ ke liye: $\Vert Ax{\Vert }^2={\sum }_i{c}_i^2{\sigma }_i^2\le {\sigma }_1^2{\sum }_i{c}_i^2={\sigma }_1^2.$ Isliye har unit $x$ ke liye $\Vert Ax\Vert \le {\sigma }_1$ hai, aur bound $x=v_1$ se hit hoti hai (tab $c_1=1$, baaki $0$, jisse $\Vert A{v}_1\Vert ={\sigma }_1$ milta hai). Isliye ${\max }_{\Vert x\Vert =1}\Vert Ax\Vert ={\sigma }_1$. $■$

Spectral Theorem se, $S=Q\Lambda Q^{\top }$ jahan $Q$ orthogonal hai aur $\Lambda =\text{diag}({\lambda }_i)$. $S^{\top }S=S^2$ compute karo (kyunki $S=S^{\top }$): $S^{\top }S=Q\Lambda Q^{\top }Q\Lambda Q^{\top }=Q{\Lambda }^2{Q}^{\top },$ $Q^{\top }Q=I$ use karke. Isliye $S^{\top }S$ ke eigenvalues ${\lambda }_i^2$ hain. Singular values: ${\sigma }_i=\sqrt{{\lambda }_i^2}=|{\lambda }_i|$. $■$ Ye kab match karte hain? ${\sigma }_i={\lambda }_i$ exactly tab hoga jab har $i$ ke liye ${\lambda }_i\ge 0$ ho — yani jab $S$ positive semi-definite ho. Agar koi eigenvalue negative hai, to uska singular value sign flip kar leta hai aur corresponding singular vector ek $-1$ absorb karta hai (into $u_i$, jaisa humne L2.1 mein dekha).

$A=U\Sigma V^{\top }$ ke determinants lo. Determinant multiplicative hai: $\det (XY)=\det X\det Y$. $\det A=\det U\cdot \det \Sigma \cdot \det V^{\top }.$ $U,V$ orthogonal $\Rightarrow \det U,\det V^{\top }\in \{+1,-1\}$ (rotations $+1$ dete hain, reflections $-1$). $\det \Sigma ={\prod }_i{\sigma }_i$ (diagonal ka product). Absolute values lene par $\pm 1$ khatam ho jaate hain: $|\det A|=|\det U||\det \Sigma ||\det V^{\top }|=1\cdot ({\prod }_i{\sigma }_i)\cdot 1={\prod }_{i=1}^n{\sigma }_i.■$ Geometry: $|\det A|$ wo factor hai jisse $A$ volumes scale karta hai. Rotations/reflections ($U,V$) volume preserve karte hain; sirf stretches ${\sigma }_i$ use change karte hain. Isliye volume scaling stretches ka product hai — exactly $\prod {\sigma }_i$. Agar koi ${\sigma }_i=0$ hai, to volume collapse ho jaata hai aur $\det A=0$.