# SVD-like matrix decomposition based on any basis?

Let's say I have a point $\mathbf{x}$ in $n$-dimensional space. For any basis $(\mathbf{u}_1, ..., \mathbf{u}_n)$, $\mathbf{x}$ can be written as a linear combination of this basis.

$\mathbf{x} = x_1 \mathbf{u}_1 + x_2 \mathbf{u}_2 + ... + x_n \mathbf{u}_n$ where each $x_i$ is a projection of $\mathbf{x}$ onto $\mathbf{u}_i$.

Now I want to generalize it to a matrix $\mathbf{X}$ in $\mathbb{R}^{m\times n}$. The Singular Value Decomposition (SVD) guarantees that any matrx $\mathbf{X}$ of rank $r$ can be written as $$\mathbf{X} = \sum_{i=1}^r \sigma_i \mathbf{u}_i \mathbf{v}^T_i$$ where $\mathbf{u}_1, ..., \mathbf{u}_r\in\mathbb{R}^m$ are orthonormal (each has length 1 and every pair is orthogonal) and $\mathbf{v}_1, ..., \mathbf{v}_r\in\mathbb{R}^n$ are also orthonormal. Each pair $\mathbf{u}_i$ and $\mathbf{v}_i$ form a pair of left and right singular vectgors with singular value $\sigma_i$.

Note that $\mathbf{u}_1, ..., \mathbf{u}_r$ is not the only orthonormal vector set in $\mathbb{R}^m$. In fact, any $r$ vectors picked from an orthonormal basis $\mathbf{u}'_1, ..., \mathbf{u}'_m\in\mathbb{R}^m$ can be a candidate. The same holds for the right singular vectors $\mathbf{v}_i$'s.

Then the question is, can I write up the SVD-like decomposition using every orthonormal basis other than left / right singular vectors? (Then the SVD can be regarded as a special case of this composition which uses left / right singular vectors.) I mean can I write something like $$\mathbf{X} = \sum_{i=1}^r \alpha_i \mathbf{s}_i \mathbf{t}^T_i$$ for every orthonormal vectors $\mathbf{s}_1, ..., \mathbf{s}_r\in\mathbb{R}^m$ and $\mathbf{t}_1, ..., \mathbf{t}_r\in\mathbb{R}^n$? If that's possible, how can I compute such $\alpha_i$'s?

-

SVDs are basically unique if all the singular values are different. (Technically, they're unique up to unit factors on the singular vectors). In the case that some singular values are the same and the SVD is not unique, you can do the following to check if particular orthonormal bases will lead to a diagonal decomposition:

Let $\mathbf{S} = [\mathbf{s}_1 ... \mathbf{s}_r] \in \mathbb{R}^{m \times r}$ and $\mathbf{T} = [\mathbf{t}_1 ... \mathbf{t}_r] \in \mathbb{R}^{n \times r}$ with $\mathbf{S}^T\mathbf{S}=\mathbf{T}^T\mathbf{T}=\mathbf{I}_r$. Compute $\mathbf{A} = \mathbf{S}^T \mathbf{X} \mathbf{T}$. If $\mbox{rank}(\mathbf{X}) = r$ and $\mathbf{A}$ is nonsingular, then $\mathbf{X} = \mathbf{SAT}^T$. In particular, if $\mathbf{A}$ is nonsingular and diagonal then its diagonal entries are your $\alpha_i$. Note this can only be true if the $\mathbf{s}_i$ are left singular vectors of $\mathbf{X}$ and $\mathbf{t}_i$ are the corresponding right singular vectors. Otherwise, $\mathbf{A}$ is either singular or nondiagonal, and no such decomposition is possible.

The intuition is that $\mathbf{A}$ is nonsingular iff the vectors $\mathbf{s}_i$ span the column space of $\mathbf{X}$ and the vectors $\mathbf{t}_i$ span its row space. If this is true, then $\mathbf{X} = \mathbf{SS}^T\mathbf{X}$ because $\mathbf{SS}^T$ is just a projector onto the column space. Likewise $\mathbf{X} = \mathbf{XTT}^T$, so $\mathbf{X} = \mathbf{SS}^T\mathbf{XTT}^T=\mathbf{SAT}^T$. Or, expressed as a sum of outer products: $$\mathbf{X} = \sum_{i=1}^r \sum_{j=1}^r a_{ij} \mathbf{s}_i \mathbf{t}_j^T$$ It's easy to see (from linear independence) that if $\mathbf{S}$ and $\mathbf{T}$ are fixed, then the coeffecients in the above decomposition are unique.

By the way, your statement "any $r$ vectors picked from a basis" should be "any $r$ vectors picked from an orthonormal basis". If the vectors are not orthonormal, but still linearly independent, then the formula generalizes like this: if $\mathbf{A} = (\mathbf{S}^T\mathbf{S})^{-1}\mathbf{S}^T \mathbf{X} \mathbf{T}(\mathbf{T}^T\mathbf{T})^{-1}$ and $\mbox{rank}(\mathbf{A})=\mbox{rank}(\mathbf{X})$, then $\mathbf{X}=\mathbf{SAT}^T$.

As an aside, a really interesting idea from recent years is that you can actually choose $\mathbf{S}$ and $\mathbf{T}$ at random, then compute the SVD of the smaller matrix $\mathbf{A}$ in order to compute the SVD of $\mathbf{X}$. This works because if $\mathbf{A} = \mathbf{U\Sigma V}^T$, then $\mathbf{X} = \mathbf{\tilde{U}\Sigma \tilde{V}}^T$, where $\mathbf{\tilde{U}}=\mathbf{SU}$ and $\mathbf{\tilde{V}}=\mathbf{TV}$. If $r$ is much smaller than $n$ or $m$, this gives huge computational savings over computing the SVD of $\mathbf{X}$ directly.

-
Thank you! By the way, can you give me any reference for the idea of choosing $\mathbf{S}$ and $\mathbf{T}$ randomly? That sounds very promising. –  Federico Magallanez Oct 30 '11 at 17:53
This paper gives a fairly comprehensive overview of what I was referring to: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions –  p.s. Oct 30 '11 at 18:22
This is a very nice answer. Thanks. –  yasmar Nov 1 '11 at 8:24

No, you cannot do this for arbitrary orthonormal sets $s_i$, $t_i$. To see this, define a function $f$ of nonzero vectors by $f(z) = \frac{\lVert Xz \rVert}{\lVert z\rVert}$, where $\lVert z \rVert = \sqrt{\sum z_i^2}$ denotes the $\ell^2$-norm. The value $f(z)$ measures the "gain" of $X$ on $z$: the factor by which $X$ scales the magnitude of the vector $z$.

Suppose $X = \sum_{i=1}^r a_i s_i t_i'$ for real numbers $0\leq a_r\leq a_{r-1}\leq \cdots \leq a_1$ and orthonormal sets of column vectors $s_i$ and $t_i$. If we decompose a vector $z$ in the domain of $f$ as $z = \sum c_i t_i$, then orthonormality of the bases $s_i$ and $t_i$ gives $f(z) = \frac{\lVert \sum c_i a_i s_i\rVert}{\lVert \sum c_i t_i\rVert} = \frac{\sqrt{\sum a_i^2 c_i^2}}{\sqrt{\sum c_i^2}}.$ Since $0\leq a_i \leq a_1$ for all $i$ by assumption, $f(z) = \frac{\sqrt{\sum a_i^2 c_i^2}}{\sqrt{\sum c_i^2}} \leq \frac{\sqrt{\sum a_1^2 c_i^2}}{\sqrt{\sum c_i^2}} = \frac{a_1\sqrt{\sum c_i^2}}{\sqrt{\sum c_i^2}} = a_1.$ This upper bound is achieved at $z = t_1$ because $f(t_i) = a_i$ for all $i$.

The function $f$ was defined in terms of the matrix $X$ and not the decomposition $X = \sum_{i=1}^r a_i s_i t_i'$, so this shows that there are restrictions on the choice of $a_1$ and $t_1$. In particular $a_1$ must be the maximum value of $f$ and $t_1$ must be a maximizer of $f$. A similar argument using $A'$ instead yields restrictions on $s_1$.

If $a_1>a_2$ then the inequality above is tight if and only if $c_i = 0$ for all $i\neq 1$. In this case the only maximizers of $f$ are scalar multiples of $t_1$. Since $t_1$ has unit norm, the above analysis determines $t_1$ up to sign (or phase in the complex case).

More generally, if $a_1 = \cdots = a_k > a_{k+1}$ for some $k$, then the inequality is tight exactly when $c_i = 0$ for $i>k$. That is to say, the maximizers of $f$ are the nonzero elements of the span of $t_1,\ldots, t_k$. Thus the analysis above only restricts $t_1$ to lie in this span.

In fact we could replace $t_1,\ldots, t_k$ by any orthonormal set $\tilde{t}_1,\ldots,\tilde{t}_k$ with the same span and replace $s_1,\ldots, s_k$ by $\tilde{s}_i = \frac{X\tilde{t}_i}{a_i}$ to obtain another decomposition $X = \sum_{i=1}^r a_i \tilde{s}_i \tilde{t}_i'$. Therefore in cases where there are repeated singular values we have some degrees of freedom in the choice of orthonormal basis.

Restricting the action of $X$ to the subspace orthogonal to $t_1,\ldots,t_k$ and repeating this argument tells you what $a_{k+1}$, $t_{k+1}$, and $s_{k+1}$ have to be, and so on. In the end, all $a_i$ are predetermined by $X$ and $t_i$ is predetermined up to sign unless $a_i = a_{i-1}$ or $a_i = a_{i+1}$.

This type of reasoning gives one way of developing the definition and properties of the SVD. Try googling "SVD variational characterization" (variational means having to do with maximizing $f$) to learn more.

-
Thank you very much for your kind answer! And I removed my post on mathoverflow.net as you suggested. –  Federico Magallanez Oct 30 '11 at 17:52