0
$\begingroup$

SVD decomposes a matrix $M$ as the product of two orthogonal matrices $U$ and $V$ (plus a diagonal matrix of singular values $\Sigma$).

$ M = U \Sigma V^*$

In this case, $U$ and $V$ are truncated to the first $n$ singular vectors for compressing $M$.

I'm exploring an alternative unconstrained factorization of $M$ using gradient descent to find $U$ and $V$ with the same dimensions as before:

$ \underset{UV}{\mathrm{argmin}} \: \mathbf{MSE}(M-UV) $

My results indicate that both methods for decomposing $M$ achieve the same mean square error ($\mathbf{MSE}$) score up to a surprising level of accuracy. Obviously, the resulting factorisations are different in each case, where the $U$ and $V$ found with the gradient descent method are not orthogonal.

My questions are:

  • Given that the second method has no constraints, I'd have supposed it should be able to find better factorisations than SVD -- in a $\mathbf{MSE}$ sense. Is this assumption right?
  • Is there any property of $M$, such as its rank or dimensions, that can be extracted from this result? The orthogonality constraint is apparently not limiting the SVD factorisation but I'm not sure if this happens in general or just for certain types of $M$.

Any thoughts about this or links to relevant literature would be greatly appreciated.

$\endgroup$
1
  • 1
    $\begingroup$ Both method should give the same approximation by EYM theorem. Note that $\Sigma V^*$ is not orthogonal to $U$. So the decomposition of $M$ to $U$ and $\Sigma V^*$ is not constrained by orthogonality $\endgroup$
    – stochastic
    Dec 23 '20 at 0:14
3
$\begingroup$

Your first question is not technically a question, but your supposition is incorrect. No, it is not true that you can find a factorization that comes closer in the mean square error sense (I assume that's what MSE stands for). The EYM theorem guarantees that the approximation attained by truncating the SVD is optimal.

Your second question is indeed a question, but I don't know what you mean by "extracting property of $M$ from this result". In particular, I don't know what you mean by "extracting", "a property of $M$", or "this result".

$\endgroup$
2
  • $\begingroup$ Thank you for your response. I have edited my question to address your points. I didn't realise EYM theorem applied to any matrix, with no constrains. Regarding the second question, I've modified the question to clarify this point but I referred to properties of M such as its rank, dimensions, orthogonality, etc. $\endgroup$
    – prl900
    Dec 22 '20 at 23:32
  • 1
    $\begingroup$ @prl900 I think this might shed some light on your questions: a matrix $M$ can be expressed in the form $M = UV$ where $U$ has $k$ columns and $V$ has $k$ rows if and only if its rank is at most $k$. On the other hand, the EYM says that among all the matrices with rank at most $k$, the product obtained by the truncated SVD is the closest one to $M$ (in the MSE sense). Note that this error will be zero if and only if $M$ itself has rank at most $k$. $\endgroup$ Dec 23 '20 at 2:46
1
$\begingroup$

Given that the second method has no constraints, I'd have supposed it should be able to find better factorisations than SVD -- in a MSE sense. Is this assumption right?

Ben is right about EYT but I'd just note that the EYT says

$$ \| A - A_k \|_2 = \bigg\| \sum_{i=k+1}^n \sigma_i u_i v_i^*\bigg\|_2 = \sigma_{k+1} $$

Uses the 2-norm which is actually the RMSE. Mean square error is $\| \cdot \|_2^2$,no? But that's neither here nor there.

I'm exploring an alternative unconstrained factorization of M using gradient descent to find U and V with the same dimensions as before

The general way the SVD is done actually is iterative. It uses Golub-Kahan-Bidiagonalization but there is another algorithm by Hestene and Stiefels that works through the gradient.

$\endgroup$
1
  • 1
    $\begingroup$ In fact, your expression for $\|A - A_k\|_2$ applies to the spectral norm as opposed to the Frobenius (sum of squares) norm, which should be $\sqrt{\sigma_k^2 + \cdots + \sigma_n^2}$. $\endgroup$ Dec 23 '20 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.