{"id":1205,"date":"2011-01-30T01:26:58","date_gmt":"2011-01-29T23:26:58","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=1205"},"modified":"2011-02-01T14:39:51","modified_gmt":"2011-02-01T12:39:51","slug":"singular-values-and-rows-distances","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2011\/01\/30\/singular-values-and-rows-distances\/","title":{"rendered":"Singular values and rows distances"},"content":{"rendered":"

Any matrix \\( {M\\in\\mathcal{M}_{m,n}} \\) maps the unit sphere to an ellipsoid. The singular values<\/em> of \\( {M} \\) are the half lenghts of the principal axes of this ellipsoid. We denote them<\/p>\n

\\[ s_1(M)\\geq\\cdots\\geq s_{\\min(n,m)}(M) \\]<\/p>\n

the \\( {\\max(m,n)-\\min(m,n)} \\) others are zero. If \\( {M^*} \\) is the conjugate transpose of \\( {M} \\) then the positive-semidefinite Hermitian matrices \\( {\\sqrt{MM^*}} \\) and \\( {\\sqrt{MM^*}} \\) share the same spectrum up to the multiplicity of \\( {0} \\), which is given by the singular values of \\( {M} \\). The singular values decomposition (SVD) theorem states that there exits unitary matrices \\( {U} \\) \\( {m\\times m} \\) and \\( {V} \\) \\( {n\\times n} \\) such that<\/p>\n

\\[ UMV=\\mathrm{diag}(s_1(M),\\ldots,s_{\\min(n,m)}(M)) \\]<\/p>\n

where we append as much zeros as needed. The largest singular value<\/p>\n

\\[ s_1(M)=\\max_{\\left|x\\right|_2=1}\\left|Mx\\right|_2=\\left|M\\right|_2 \\]<\/p>\n

is the operator norm of \\( {M} \\). For the smallest we have<\/p>\n

\\[ s_{\\min(n,m)}(M)=\\min_{\\left|x\\right|_2=1}\\left|Mx\\right|_2. \\]<\/p>\n

The matrix \\( {M} \\) has \\( {\\mathrm{rank}(M)} \\) non zero singular values. The matrix \\( {M} \\) is invertible iff \\( {m=n} \\) and \\( {s_n(M)>0} \\) and in this case \\( {s_n(M)=\\left|M^{-1}\\right|_2^{-1}} \\). If \\( {m=n} \\) and \\( {M} \\) is normal (i.e. \\( {MM^*=M^*M} \\)) then the singular values of \\( {M} \\) are the modules of the eigenvalues of \\( {M} \\).<\/p>\n

If \\( {m=n} \\) and \\( {M} \\) has rows \\( {R_1,\\ldots,R_n} \\) then by viewing \\( {\\left|\\det(M)\\right|} \\) as a hyperparallelogram volume,<\/p>\n

\\[ |\\det(M)|=\\prod_{k=1}^ns_k(M) =\\prod_{k=1}^n\\mathrm{dist}(R_k,\\mathrm{span}\\{R_1,\\ldots,R_{k-1}\\}). \\]<\/p>\n

Here are two additional nice facts relating singular values with rows distances, due to Rudelson<\/a> and Vershynin<\/a> [CPAM 2009<\/a>] and Tao<\/a> and Vu<\/a> [AoP 2010<\/a>].<\/p>\n

Lemma 1 (Rudelson and Vershynin)<\/b> <\/a> If \\( {M\\in\\mathcal{M}_{m,n}(K)} \\) has rows \\( {R_1,\\ldots,R_m} \\), then, denoting \\( {R_{-i}=\\mathrm{span}\\{R_j:j\\neq i\\}} \\), we have<\/em> <\/p>\n

\\[ m^{-1\/2}\\min_{1\\leq i\\leq m}\\mathrm{dist}_2(R_i,R_{-i}) \\leq s_{\\min(m,n)}(M) \\leq \\min_{1\\leq i\\leq m}\\mathrm{dist}_2(R_i,R_{-i}). \\]<\/em><\/p>\n<\/blockquote>\n

Proof:<\/em> Since \\( {M} \\) and \\( {M^\\top} \\) have same singular values, we can prove the statement for the columns of \\( {M} \\). For every vector \\( {x\\in K^n} \\) and every \\( {i\\in\\{1,\\ldots,n\\}} \\), the triangle inequality and the identity \\( {Mx=x_1C_1+\\cdots+x_n C_n} \\) give<\/p>\n

\\[ \\left|Mx\\right|_2 \\geq \\mathrm{dist}_2(Mx,C_{-i}) =\\min_{y\\in C_{-i}} \\left|Mx-y\\right|_2 =\\min_{y\\in C_{-i}} \\left|x_iC_i-y\\right|_2 =\\vert x_i\\vert\\mathrm{dist}_2(C_i,C_{-i}). \\]<\/p>\n

If \\( {\\left|x\\right|_2 =1} \\) then necessarily \\( {\\vert x_i\\vert \\geq n^{-1\/2}} \\) for some \\( {i\\in\\{1,\\ldots,n\\}} \\), and therefore<\/p>\n

\\[ s_{\\min(m,n)}(M) =\\min_{\\left|x\\right|_2 =1}\\left|Mx\\right|_2 \\geq n^{-1\/2}\\min_{1\\leq i\\leq n}\\mathrm{dist}_2(C_i,C_{-i}). \\]<\/p>\n

Conversely, for any \\( {i\\in\\{1,\\ldots,n\\}} \\), there exists a vector \\( {y\\in K^n} \\) with \\( {y_i=1} \\) such that<\/p>\n

\\[ \\mathrm{dist}_2(C_i,C_{-i}) =\\left|y_1C_1+\\cdots+y_nC_n\\right|_2 =\\left|My\\right|_2 \\geq \\left|y\\right|_2 \\min_{\\left|x\\right|_2=1}\\left|Mx\\right|_2 \\geq s_{\\min(m,n)}(M) \\]<\/p>\n

where we used the fact that \\( {\\left|y\\right|^2_2 = |y_1|^2+\\cdots+|y_n|^2\\geq |y_i|^2=1} \\). ☐<\/p>\n

Lemma 2 (Tao and Vu)<\/b> Let \\( {1\\leq m\\leq n} \\) and \\( {M\\in\\mathcal{M}_{m,n}(K)} \\) with rows \\( {R_1,\\ldots,R_m} \\). If \\( {\\mathrm{rank}(M)=m} \\) then, denoting \\( {R_{-i}=\\mathrm{span}\\{R_j:j\\neq i\\}} \\), we have<\/em> <\/p>\n

\\[ \\sum_{i=1}^ms_i^{-2}(M)=\\sum_{i=1}^m\\mathrm{dist}_2(R_i,R_{-i})^{-2}. \\]<\/em><\/p>\n<\/blockquote>\n

Proof:<\/em> The orthogonal projection of \\( {R_i} \\) on \\( {R_{-i}} \\) is \\( {B^*(BB^*)^{-1}BR_i^*} \\) where \\( {B} \\) is the \\( {(m-1)\\times n} \\) matrix obtained from \\( {M} \\) by removing the row \\( {R_i} \\). In particular, we have<\/p>\n

\\[ \\left| R_i\\right|_2^2-\\mathrm{dist}_2(R_i,R_{-i})^2 =\\left| B^*(BB^*)^{-1}BR_i^*\\right|_2^2 = (BR_i^*)^*(BB^*)^{-1}BR_i^* \\]<\/p>\n

by the Pythagoras theorem. On the other hand, the Schur bloc inversion formula states that if \\( {M} \\) is an \\( {m\\times m} \\) matrix then for every partition \\( {\\{1,\\ldots,m\\}=I\\cup I^c} \\),<\/p>\n

\\[ (M^{-1})_{I,I}=(M_{I,I}-M_{I,I^c}(M_{I^c,I^c})^{-1}M_{I^c,I})^{-1}. \\]<\/p>\n

Now we take \\( {M=MM^*} \\) and \\( {I=\\{i\\}} \\), and we note that \\( {(MM^*)_{i,j}=R_i\\cdot R_j} \\), which gives<\/p>\n

\\[ ((MM^*)^{-1})_{i,i}=(R_i\\cdot R_i-(BR_i^*)^*(BB^*)^{-1}BR_i^*)^{-1} =\\mathrm{dist}_2(R_i,R_{-i})^{-2}. \\]<\/p>\n

The desired formula follows by taking the sum over \\( {i\\in\\{1,\\ldots,m\\}} \\). ☐<\/p>\n","protected":false},"excerpt":{"rendered":"

Any matrix \\( {M\\in\\mathcal{M}_{m,n}} \\) maps the unit sphere to an ellipsoid. The singular values of \\( {M} \\) are the half lenghts of the…<\/p>\n

Continue readingSingular values and rows distances<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":102},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1205"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=1205"}],"version-history":[{"count":12,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1205\/revisions"}],"predecessor-version":[{"id":1255,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/1205\/revisions\/1255"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=1205"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=1205"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=1205"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}