Relationship between Alternating Least Squares and SVD

Question

I have been assuming that ALS is simply an alternative algorithm for doing matrix decomposition that is more efficient, but in the end produces the same $U$ & $V$ matrices that SVD does. Is this true?

Answer 1

Actually, ALS is generally less computationally efficient than directly computing the SVD solution, with some special cases.

An interesting results of the SVD decomposition is that one gets the complete nested set of low-rank approximations. So if you'd like a rank 5 approximation and a rank 10 approximation, you can just compute the full SVD, grab the top 5 components from that decomposition to form the rank 5 approximation with the lowest MSE and grab the top 10 components for the rank 10 approximation with the lowest MSE.

Meanwhile, ALS only gives you a single rank approximation. So if you wanted a rank 5 and rank 10 decomposition, you would need to run the ALS algorithm twice.

On the other hand, SVD requires that all entries of the matrix be observed. This is not the case for ALS. Similarly, ALS easily generalizes to higher order cases (i.e., tensors) while SVD does not.

Finally, resulting $U$ and $V$ between the two algorithms are not necessarily the same: for one, SVD results in $UDV^T$, while ALS results in only $UV^T$. What is true is that, assuming convergence to the global minimum by ALS, we should have that $UDV^T$ = $\tilde U \tilde V^T$, where $UDV^T$ is the SVD solution and $\tilde U \tilde V^T$ is the ALS solution.

In fact, there's no guarantees whatsoever about $\tilde U$ and $\tilde V$ as the solution from an ALS problem. Note that $( \tilde U \alpha) (\tilde V \alpha^{-1})^T$ = $\tilde U \tilde V^T$, which means that if $\tilde U \tilde V^T$ is the solution to an ALS problem, then so is $(\tilde U \alpha) (\tilde V \alpha^{-1})^T$. However, the constraints required for an SVD solution doesn't allow for this type of ambiguity.

Answer 2

A rank-1 solution by alternating least squares is a linear transformation of a rank-1 SVD.

A rank-2 solution by alternating least squares (WH) is related to SVD (UDV), where the second singular vector U_2 is a linear transformation of W_1 - W_2, similarly V_2 is a linear transformation of H_1 - H_2.

ALS is always the fastest method for solving a rank-2 SVD (based on my current work), significantly faster than lanczos bidiagonalization in irlba, for example.

At rank-3 the vectors in SVD and NMF are no longer directly relatable. This is because alternating least squares seeks factors that best describe the signal collectively, rather than SVD which seeks first one factor which best describes the signal, then an additional factor that describes the next most signal given the normalization of the first factor, and so on.

The above intuition immediately makes obvious how alternating least squares can be used to solve an SVD. We solve a k = 1 ALS solution, fix the first vector, randomly initialize a second vector, solve that vector while holding the first vector fixed by ALS, and repeat until reaching the desired rank. This works really well, in fact, it's less costly than Lanczos bidiagonalization (i.e. irlba) because it generally involves only 1-2 refinement iterations per rank addition.

The previously described intuition also highlights just how different SVD and ALS MF are in their objectives, and hence proper applications. They are not at all describing similar information. One way to think of SVD is that the first vector in SVD is a normalization of the data to a middle point, the second factor is a normalization of the data based on the preceding normalization, and so on. The result is that there are positive and negative vectors which account for prior local over- or under-normalization. Thus, the significance of an arbitrary nth vectors can only be determined given the preceding vectors and is not particularly intuitive. It is therefore useful for describing variance in signals, but not signals themselves, although it incidentally may extract recognizable signals at times.

Note that SVD solutions and ALS SVD solutions are linear transformations of one another, they describe the same relationships between data but are not on the same scale. In general, this is not a concern.

Because factors in NMF are dependent on one another during the alternating updates, it takes more alternating updates to converge on the minima. In SVD, because other factors are fixed with each update and there is only a single vector to be added, there are fewer alternating updates with each rank addition. Whether ALS MF or SVD is faster all depends on the condition of your dataset and the rank you're requiring.

As @Cliff AB pointed out, SVD is rank-indefinite, meaning you can run a 5-rank decomposition or a 10-rank decomposition and get the same first five vectors. This is attractive, but does not guarantee robustness between similar datasets. ALS MF does not have such a rank-definite guarantee, but in general can extract signals from two different datasets that are highly correlated. This means that cross-validation for rank determination is necessary for NMF, and in general for datasets with robust signal there will be a best rank. Now THIS is not fast, and so ALS MF, even if it's faster one-off than an SVD, becomes quite burdensome to do properly.