Probably useful for my 🗺️ PhD Plan to reduce the size of the Neural networks used.
Matrices: the Eckart-Young theorem
The Eckart–Young theorem states that for matrices the best low-rank approximation problem is well posed and solved by truncating the singular value decomposition. Let have singular value decomposition with , and define . Then for every with :
The Frobenius minimiser is unique iff . Mirsky extended the statement to every unitarily invariant norm.
Proof (spectral norm). Since , , while has dimension , so the two subspaces share a unit vector . Then
Proof (Frobenius norm). Weyl’s inequality for singular values gives . Take , and , so that :
Why tensors differ
The paper (V. de Silva and L.-H. Lim) shows that for tensors of order the analogue fails: the set of tensors of rank is in general not closed, so a best rank approximation need not exist. The standard example, for linearly independent , is
which has rank but is a limit of rank tensors (its border rank is ). Minimising sequences then diverge in norm, with the two rank one terms cancelling, which is the degeneracy seen in CP decompositions.
For compressing Neural networks this means: truncated SVD of a weight matrix is provably optimal (Eckart-Young), whereas low CP rank compression of higher order weight tensors can be ill posed; Tucker or tensor train formats, whose sets of bounded multilinear rank are closed, avoid this.