1

So - I know if you perform SVD to a matrix $X$, you can then use Echkart Young theorem to get the best rank $r$ approximation $\overline{X}$ to $X$ possible. Since the resultant ${\overline{X}}$ will be of a lower rank, that means some of the rows will be linear combinations of the others, and so rather than store all of ${\overline{X}}$ you could simply store some of the rows of ${\overline{X}}$, with the combinations required to achieve the other rows. So it's a sort of "compression" technique.

Does this make sense/would it be sensible to do? I know there are clearly going to be better compression techniques out there, I'm just asking if in theory this would indeed provide a sort of lossy compression. Thanks!

kjetil b halvorsen
  • 77,844
Riemann'sPointyNose
  • 133
  • Are you asking if choosing $r$ equal to the rank of $X$ means that the SVD reconstruction is lossless? – Sycorax Jan 19 '21 at 19:27
  • @Sycorax sorry, I meant to say lossy. If I choose the rank $r$ to be less than the rank of $X$ – Riemann'sPointyNose Jan 19 '21 at 19:28
  • Is $X^*$ the same as $\overline{X}$? – Sycorax Jan 19 '21 at 19:29
  • @Sycorax sorry again yeah I'm really messing up xD I was using $*$ here to try to show I was correcting what I was saying, not as some new object. Apologies xD – Riemann'sPointyNose Jan 19 '21 at 19:30
  • @Sycorax overall I'm basically asking if I do SVD and find a low rank approximation of some data matrix, does this make sense to use as a lossy compression technique? – Riemann'sPointyNose Jan 19 '21 at 19:30
  • SVD of $X \in \mathbb{R}^{n\times p}$ for some $r<p$ stores an $r$-vector, a $n \times r$ matrix and an $r \times p$ matrix. Whenever $r < \text{rank}(X)$, we know that the reconstruction has error, so it is "lossy." But if by "compression" you mean that we store fewer elements, that depends on the values of $r,n,p$ because the storage cost of the SVD could be larger or smaller than the storage cost of $X$ itself. – Sycorax Jan 19 '21 at 19:33
  • 1
    It's definitely possible to use the SVD for compression, and often with images, e.g. http://www.math.utah.edu/~goller/F15_M2270/BradyMathews_SVDImage.pdf – jld Jan 19 '21 at 20:35
  • 2
    See also https://stats.stackexchange.com/questions/177102/what-is-the-intuition-behind-svd/179042#179042 – kjetil b halvorsen Jan 20 '21 at 01:01

0 Answers0