The singular value decomposition is great and it even works well for complex and quaternionic matrices (and we can even generalize decompositions like the spectral, polar, and singular value decomposition and apply them to bounded linear operators between infinite dimensional Hilbert spaces), but to get a better appreciation of the singular value decomposition, we ought to analyze its deficiencies as well. I am currently researching other linear dimensionality reduction techniques (namely LSRDRs) that work well in the cases when the singular value decomposition is not the best technique to use for a linear dimensionality reduction. These cases include the following:
While the SVD approximates a matrix with a low rank matrix, it does not generalize that well to higher order SVDs that decompose tensors in V1⊗V2⊗⋯⊗Vn where V1,…,Vn are vector spaces.
The SVD works applies to linear mappings between inner product spaces, but the SVD does not take any additional structure that the linear mappings or inner product spaces have. For example, if we had a tuple of vectors (v1,…,vr), then we may want to use a linear dimensionality reduction that does not just consider (v1,…,vr) as a matrix. For example, it is more meaningful to consider a weight matrix in a neural network as a tuple of row vectors or a tuple of column vectors than just a matrix without additional structure.
If we apply the principal component analysis to a collection (v1,…,vr) of vectors (with mean 0 for simplicity), then the k-dimensional subspace M that best approximates (v1,…,vr) may fail to cluster together. For example, suppose that X1,…,Xs,Y1,…,Ys are independent normally distributed random variables each with mean 0 where each Xj has covariance matrix In⊕0.1⋅In while each Yj has covariance matrix 0.1⋅In⊕In. If we take a random sample (x1,…,xs,y1,…,ys) from X1,…,Xs,Y1,…,Ys and then perform a principal component analysis to (x1,…,xs,y1,…,ys) to find an n-dimensional subspace of Rn⊕Rn, then the principal component analysis will not tell you anything meaningful. We would ideally want to use something similar to the principal component analysis but which instead returns subspaces that are near Rn⊕{0} or {0}⊕Rn. The principal component analysis returns the top k-dimensional affine subspace of a vector space in magnitude, but the principal component analysis does not care if the canonical basis for these k-dimensions form a cluster in any way.
Every real, complex, or quaternionic matrix has an SVD, and the SVD is unique (except in the case where we have repeated singular values). While mathematicians tend to like it when something exists and is unique, and computer scientists may find the existence and uniqueness of the singular value decomposition to be useful, the existence and uniqueness of the SVD does have its weaknesses (and existence and uniqueness theorems imply a sort of simplicity that is not the best indicator of good mathematics; good mathematics is often more complicated than what you would get from a simple existence and uniqueness result). One should consider the SVD as a computer program, programming language, and piece of code that always return an output regardless of whether the output makes sense without ever producing an error message. This makes it more difficult to diagnose a problem or determine whether one is using the correct tools in the first place, and this applies to the singular value decomposition as well. The poor behavior of an algorithm could also provide some useful information. For example, suppose that one is analyzing a block cipher round function E using an algorithm L. If the algorithm L produces errors for complicated block cipher round functions but does not produce these errors for simple block cipher round functions, then the presence of one or more errors indicates that the block cipher round function E is secure.
If A is a real matrix, but we take the complex or quaternionic SVD of A to get a factorization A=UDV∗, then the matrices U,V will be real orthogonal matrices instead of complex or quaternionic matrices. This means that the SVD of a matrix is always well-behaved which is again a problem since this well-behavedness does not necessarily mean that the singular value decomposition is useful for whatever circumstances we are using it for and the poor behavior of a process may provide useful information.
The SVD is not exactly new or cutting edge, so it will give one only a limited amount of information about matrices or other objects.
Let K denote either the field of real numbers, the field complex numbers, or the division ring of quaternions. Suppose that A1,…,Ar are n×n-matrices with entries in K. If X1,…,Xr are d×d-matrices, then define an superoperator Γ(A1,…,Ar;X1,…,Xr):Mn,d(K)→Mn,d(K) by letting Γ(A1,…,Ar;X1,…,Xr)(X)=A1XX∗1+⋯+ArXX∗r whenever X∈Mn,d(K). Define a partial (but nearly total) function FA1,…,Ar;K:Md(K)r→[0,∞) by letting
FA1,…,Ar;K(X1,…,Xr)=ρ(Γ(A1,…,Ar;X1,…,Xr))ρ(Φ(X1,…,Xr))1/2. Here, let ρ denote the spectral radius of a linear operator. We say that (X1,…,Xr) is a L2,d-spectral radius dimensionality reduction (LSRDR) of type K if the quantityFA1,…,Ar;K(X1,…,Xr) is locally maximized.
One can compute LSRDRs using a flavor of gradient ascent. Don’t worry. Taking an approximate gradient of the FA1,…,Ar;K is less computationally costly than it sounds, and the gradient ascent should converge to an LSRDR (X1,…,Xr). If the gradient ascent process fails to quickly converge to an LSRDR (X1,…,Xr), then LSRDRs may not be the best tool to use.
We say that (X1,…,Xr),(Y1,…,Yr) are projectively similar and write (X1,…,Xr)≃K(Y1,…,Yr) if there is some α∈Z(K) (Z(K) denotes the center of K) and some invertible matrix R such that Xj=αRYjR−1 for 1≤j≤r. Let [X1,…,Xr]K denote the equivalence class containing (X1,…,Xr).
The equivalence class [X1,…,Xr]K of an LSRDR of type K of (A1,…,Ar) is often unique. At the very least, one should only be able to find a few equivalence classes [X1,…,Xr]K of LSRDRS of type K of (A1,…,Ar), and the equivalence class [X1,…,Xr]K of LSRDRs with highest fitness should also be the easiest to find. But if the equivalence class [X1,…,Xr]K is far from being unique, then this should be an indicator that the notion of taking an LSRDR may not be the best tool to use for analyzing (A1,…,Ar), so one should try something else in this case.
If A1,…,Ar are all real matrices but K=C, then the equivalence class [X1,…,Xr]K of the LSRDR should contain a tuple (Y1,…,Yr) where each Yi is a real matrix. One can quickly test whether one should be able to find such a tuple (Y1,…,Yr) given an LSRDR (X1,…,Xr) is to compute Tr(Xi)Tr(Xj). If Tr(Xi)Tr(Xj) is a real number (up-to a rounding error), then that means that the LSRDR is well-behaved and perhaps an appropriate tool to use, but otherwise the LSRDR may not be the best tool to use.
If we find our LSRDR (X1,…,Xr) of type K of (A1,…,Ar), then if everything works out well, there should be some matrices R,S where Xj=RAjS for 1≤j≤s and where RS=λ⋅1d and where SR=λ⋅P for some (not necessarily orthogonal) projection matrix P and constant λ∈Z(K). If λ=1, then we say that R,S is constant factor normalized; if R,S is constant factor normalized, then RS=1d,SR=P, so let us assume that R,S is constant factor normalized to make everything simpler. Let UR be the dominant eigenvector of Γ(A1,…,Ar;X1,…,Xr), and let UL be the dominant eigenvector of Γ(A1,…,Ar;X1,…,Xr). Then there are positive semidefinite matrices G,H and non-zero constants μG,μH∈Z(K) whereURS∗=μH⋅H,ULR=μG⋅G. The projection matrix P should be recovered from the positive semidefinite matrices G,H since Im(H)=Im(P),Im(G)=ker(P)⊥, and the positive semidefinite matrices G,H (up-to a constant real factor) should be uniquely determined. The positive semidefinite matrices G,H should be considered to be the dominant clusters of dimensions for (A1,…,Ar).
Order 2 tensors: Suppose that v1,…,vr∈V for some finite dimensional real inner product space V. Then set Aj=vjv∗j for 1≤j≤r. Then G=H, so the positive semidefinite matrix G is our desired dimensionality reduction of v1,…,vr. For example, if M is a weight matrix in a neural network, then we can make v1,…,vr the columns of M, or we can make v1,…,vr the transposes of the rows of M. Since we apply activation functions before and after we apply M, it makes sense to separate M into rows and columns this way. And yes, I have performed computer experiments that indicate that for Aj=vjv∗j, the matrices G,H do represent a cluster of dimensions (at least sometimes) rather than simply the top d dimensions. I have done the experiment where (v1,…,vr)=(x1,…,xs,y1,…,ys) and in this experiment, the matrices G,H,P (up to a constant factor for G,H) are all approximately the projection matrix that projects onto the subspace Rn⊕{0}.
Order 3 tensors: Suppose that V,W are finite dimensional real or complex inner product spaces and A:V→V⊗W is a linear mapping. Observe that L(V,V⊗W) is canonically isomorphic to V⊗V⊗W. Now give W an orthonormal basis e1,…,er, and set Aj=(1V⊗e∗j)A for 1≤j≤r. Then one can apply an LSRDR to A1,…,Ar to obtain the positive semidefinite matrices G,H. The positive semidefinite matrices G,H do not depend on the orthonormal basis e1,…,er that we choose. For example, suppose that O1,O2 are open subsets of Euclidean spaces of possibly different dimensions and f:O1→O2 is a C2-function where there are f1,…,fr:O1→R where f(x)=(f1(x),…,fr(x)) for each x∈O1. Then let Aj=H(fj)(x) for 1≤j≤r where H(fj) denotes the Hessian of fj. Then the matrices G,H of an LSRDR of A1,…,Ar represent a cluster of dimensions in the tangent space at the point x.
Order 4 tensors: Given a vector space V, let L(V) denote the collection of linear maps from V to V. Let V be a finite dimensional complex inner product space. Then there are various ways to put V⊗V⊗V⊗V into a canonical one-to-one correspondence with L(L(V)). Furthermore, the Choi representation gives a one-to-one correspondence between the completely positive operators in L(L(V)) and the positive semidefinite operators in L(V⊗V). An operator E∈L(L(V)) is completely positive if and only if there are A1,…,Ar∈L(V) where E(X)=A1XA∗1+⋯+ArXA∗r for all X∈L(V). Therefore, whenever E is completely positive, we compute a complex LSRDR (X1,…,Xr) of (A1,…,Ar), and we should get matrices R,S,P,G,H, and G,H give us our desired dimensionality reduction. Of course, given an order 4 tensor, one has to ask whether it is appropriate to use LSRDRs for this order 4 tensor, and one should ask about the best way to use these order 4 tensors to produce an LSRDR.
If this comment were not long enough already, I would give an explanation for why I believe LSRDRs often behave well, but this post is really about the SVDs so I will save my math for another time.
The singular value decomposition is great and it even works well for complex and quaternionic matrices (and we can even generalize decompositions like the spectral, polar, and singular value decomposition and apply them to bounded linear operators between infinite dimensional Hilbert spaces), but to get a better appreciation of the singular value decomposition, we ought to analyze its deficiencies as well. I am currently researching other linear dimensionality reduction techniques (namely LSRDRs) that work well in the cases when the singular value decomposition is not the best technique to use for a linear dimensionality reduction. These cases include the following:
While the SVD approximates a matrix with a low rank matrix, it does not generalize that well to higher order SVDs that decompose tensors in V1⊗V2⊗⋯⊗Vn where V1,…,Vn are vector spaces.
The SVD works applies to linear mappings between inner product spaces, but the SVD does not take any additional structure that the linear mappings or inner product spaces have. For example, if we had a tuple of vectors (v1,…,vr), then we may want to use a linear dimensionality reduction that does not just consider (v1,…,vr) as a matrix. For example, it is more meaningful to consider a weight matrix in a neural network as a tuple of row vectors or a tuple of column vectors than just a matrix without additional structure.
If we apply the principal component analysis to a collection (v1,…,vr) of vectors (with mean 0 for simplicity), then the k-dimensional subspace M that best approximates (v1,…,vr) may fail to cluster together. For example, suppose that X1,…,Xs,Y1,…,Ys are independent normally distributed random variables each with mean 0 where each Xj has covariance matrix In⊕0.1⋅In while each Yj has covariance matrix 0.1⋅In⊕In. If we take a random sample (x1,…,xs,y1,…,ys) from X1,…,Xs,Y1,…,Ys and then perform a principal component analysis to (x1,…,xs,y1,…,ys) to find an n-dimensional subspace of Rn⊕Rn, then the principal component analysis will not tell you anything meaningful. We would ideally want to use something similar to the principal component analysis but which instead returns subspaces that are near Rn⊕{0} or {0}⊕Rn. The principal component analysis returns the top k-dimensional affine subspace of a vector space in magnitude, but the principal component analysis does not care if the canonical basis for these k-dimensions form a cluster in any way.
Every real, complex, or quaternionic matrix has an SVD, and the SVD is unique (except in the case where we have repeated singular values). While mathematicians tend to like it when something exists and is unique, and computer scientists may find the existence and uniqueness of the singular value decomposition to be useful, the existence and uniqueness of the SVD does have its weaknesses (and existence and uniqueness theorems imply a sort of simplicity that is not the best indicator of good mathematics; good mathematics is often more complicated than what you would get from a simple existence and uniqueness result). One should consider the SVD as a computer program, programming language, and piece of code that always return an output regardless of whether the output makes sense without ever producing an error message. This makes it more difficult to diagnose a problem or determine whether one is using the correct tools in the first place, and this applies to the singular value decomposition as well. The poor behavior of an algorithm could also provide some useful information. For example, suppose that one is analyzing a block cipher round function E using an algorithm L. If the algorithm L produces errors for complicated block cipher round functions but does not produce these errors for simple block cipher round functions, then the presence of one or more errors indicates that the block cipher round function E is secure.
If A is a real matrix, but we take the complex or quaternionic SVD of A to get a factorization A=UDV∗, then the matrices U,V will be real orthogonal matrices instead of complex or quaternionic matrices. This means that the SVD of a matrix is always well-behaved which is again a problem since this well-behavedness does not necessarily mean that the singular value decomposition is useful for whatever circumstances we are using it for and the poor behavior of a process may provide useful information.
The SVD is not exactly new or cutting edge, so it will give one only a limited amount of information about matrices or other objects.
Let K denote either the field of real numbers, the field complex numbers, or the division ring of quaternions. Suppose that A1,…,Ar are n×n-matrices with entries in K. If X1,…,Xr are d×d-matrices, then define an superoperator Γ(A1,…,Ar;X1,…,Xr):Mn,d(K)→Mn,d(K) by letting Γ(A1,…,Ar;X1,…,Xr)(X)=A1XX∗1+⋯+ArXX∗r whenever X∈Mn,d(K). Define a partial (but nearly total) function FA1,…,Ar;K:Md(K)r→[0,∞) by letting
FA1,…,Ar;K(X1,…,Xr)=ρ(Γ(A1,…,Ar;X1,…,Xr))ρ(Φ(X1,…,Xr))1/2. Here, let ρ denote the spectral radius of a linear operator. We say that (X1,…,Xr) is a L2,d-spectral radius dimensionality reduction (LSRDR) of type K if the quantityFA1,…,Ar;K(X1,…,Xr) is locally maximized.
One can compute LSRDRs using a flavor of gradient ascent. Don’t worry. Taking an approximate gradient of the FA1,…,Ar;K is less computationally costly than it sounds, and the gradient ascent should converge to an LSRDR (X1,…,Xr). If the gradient ascent process fails to quickly converge to an LSRDR (X1,…,Xr), then LSRDRs may not be the best tool to use.
We say that (X1,…,Xr),(Y1,…,Yr) are projectively similar and write (X1,…,Xr)≃K(Y1,…,Yr) if there is some α∈Z(K) (Z(K) denotes the center of K) and some invertible matrix R such that Xj=αRYjR−1 for 1≤j≤r. Let [X1,…,Xr]K denote the equivalence class containing (X1,…,Xr).
The equivalence class [X1,…,Xr]K of an LSRDR of type K of (A1,…,Ar) is often unique. At the very least, one should only be able to find a few equivalence classes [X1,…,Xr]K of LSRDRS of type K of (A1,…,Ar), and the equivalence class [X1,…,Xr]K of LSRDRs with highest fitness should also be the easiest to find. But if the equivalence class [X1,…,Xr]K is far from being unique, then this should be an indicator that the notion of taking an LSRDR may not be the best tool to use for analyzing (A1,…,Ar), so one should try something else in this case.
If A1,…,Ar are all real matrices but K=C, then the equivalence class [X1,…,Xr]K of the LSRDR should contain a tuple (Y1,…,Yr) where each Yi is a real matrix. One can quickly test whether one should be able to find such a tuple (Y1,…,Yr) given an LSRDR (X1,…,Xr) is to compute Tr(Xi)Tr(Xj). If Tr(Xi)Tr(Xj) is a real number (up-to a rounding error), then that means that the LSRDR is well-behaved and perhaps an appropriate tool to use, but otherwise the LSRDR may not be the best tool to use.
If we find our LSRDR (X1,…,Xr) of type K of (A1,…,Ar), then if everything works out well, there should be some matrices R,S where Xj=RAjS for 1≤j≤s and where RS=λ⋅1d and where SR=λ⋅P for some (not necessarily orthogonal) projection matrix P and constant λ∈Z(K). If λ=1, then we say that R,S is constant factor normalized; if R,S is constant factor normalized, then RS=1d,SR=P, so let us assume that R,S is constant factor normalized to make everything simpler. Let UR be the dominant eigenvector of Γ(A1,…,Ar;X1,…,Xr), and let UL be the dominant eigenvector of Γ(A1,…,Ar;X1,…,Xr). Then there are positive semidefinite matrices G,H and non-zero constants μG,μH∈Z(K) whereURS∗=μH⋅H,ULR=μG⋅G. The projection matrix P should be recovered from the positive semidefinite matrices G,H since Im(H)=Im(P),Im(G)=ker(P)⊥, and the positive semidefinite matrices G,H (up-to a constant real factor) should be uniquely determined. The positive semidefinite matrices G,H should be considered to be the dominant clusters of dimensions for (A1,…,Ar).
Order 2 tensors: Suppose that v1,…,vr∈V for some finite dimensional real inner product space V. Then set Aj=vjv∗j for 1≤j≤r. Then G=H, so the positive semidefinite matrix G is our desired dimensionality reduction of v1,…,vr. For example, if M is a weight matrix in a neural network, then we can make v1,…,vr the columns of M, or we can make v1,…,vr the transposes of the rows of M. Since we apply activation functions before and after we apply M, it makes sense to separate M into rows and columns this way. And yes, I have performed computer experiments that indicate that for Aj=vjv∗j, the matrices G,H do represent a cluster of dimensions (at least sometimes) rather than simply the top d dimensions. I have done the experiment where (v1,…,vr)=(x1,…,xs,y1,…,ys) and in this experiment, the matrices G,H,P (up to a constant factor for G,H) are all approximately the projection matrix that projects onto the subspace Rn⊕{0}.
Order 3 tensors: Suppose that V,W are finite dimensional real or complex inner product spaces and A:V→V⊗W is a linear mapping. Observe that L(V,V⊗W) is canonically isomorphic to V⊗V⊗W. Now give W an orthonormal basis e1,…,er, and set Aj=(1V⊗e∗j)A for 1≤j≤r. Then one can apply an LSRDR to A1,…,Ar to obtain the positive semidefinite matrices G,H. The positive semidefinite matrices G,H do not depend on the orthonormal basis e1,…,er that we choose. For example, suppose that O1,O2 are open subsets of Euclidean spaces of possibly different dimensions and f:O1→O2 is a C2-function where there are f1,…,fr:O1→R where f(x)=(f1(x),…,fr(x)) for each x∈O1. Then let Aj=H(fj)(x) for 1≤j≤r where H(fj) denotes the Hessian of fj. Then the matrices G,H of an LSRDR of A1,…,Ar represent a cluster of dimensions in the tangent space at the point x.
Order 4 tensors: Given a vector space V, let L(V) denote the collection of linear maps from V to V. Let V be a finite dimensional complex inner product space. Then there are various ways to put V⊗V⊗V⊗V into a canonical one-to-one correspondence with L(L(V)). Furthermore, the Choi representation gives a one-to-one correspondence between the completely positive operators in L(L(V)) and the positive semidefinite operators in L(V⊗V). An operator E∈L(L(V)) is completely positive if and only if there are A1,…,Ar∈L(V) where E(X)=A1XA∗1+⋯+ArXA∗r for all X∈L(V). Therefore, whenever E is completely positive, we compute a complex LSRDR (X1,…,Xr) of (A1,…,Ar), and we should get matrices R,S,P,G,H, and G,H give us our desired dimensionality reduction. Of course, given an order 4 tensor, one has to ask whether it is appropriate to use LSRDRs for this order 4 tensor, and one should ask about the best way to use these order 4 tensors to produce an LSRDR.
If this comment were not long enough already, I would give an explanation for why I believe LSRDRs often behave well, but this post is really about the SVDs so I will save my math for another time.