1
$\begingroup$

Suppose we have a matrix X that has dimension $m$ x $n$, then we need to store $m$ x $n$ numbers to describe this matrix. For example, for matrix

$$ \begin{matrix} 1 & 2 & 5\\ 3 & 4 & 0\\ \end{matrix} $$

We stored 5 numbers to describe it and saved one space to store element 0. However, if we have a very large $m$ x $n$ matrix, we might want to use SVD for approximation.

My question is that when given such a X matrix, whose dimension is for example $1000$ * $1200$, then SVD would give us U,S,$V^t$ = X, and U is $1000$ * $1000$, S is $1000$ * $1200$, and V is $1200$ * $1200$. So in this case, how can we find those singular values that have 0 as its diagonal entry, and then we can store less numbers?

Or I should say how can we use some decompositions(SVD, eigen decomposition) to reduce the number of elements needed to describe a matrix?

Thank you!

$\endgroup$
0
$\begingroup$

In general, what you ask is a near impossibility as every zero singular value which will be computed as a small nonzero number, rather than a perfect zero. This is a consequence of rounding errors.

However, if you will settle for approximations rather than attempt an exact approximation, then you can compute the full SVD and truncate it, i.e. discard all singular vectors corresponding to singular values which are less than your chosen threshold. This is one strategy which is some times employed in image compression, although I must hasten to say that more advanced algorithms exist. The 2-norm of the error equals the largest singular value which is discarded.

There are algorithms which seek to compute the dominant singular values/vectors so that one does not have to compute and truncate the full SVD.

Many matrices are naturally sparse, i.e. the vast majority of all entries a zero. Prime examples are models of real life structures. The matrices are sparse because each, say, beam is connected to a small number of neighbors. For sparse matrices there are a variety of specialized storage formats which encode the location of the nonzero entries and their values. The simplest formats is COO (coordinate format), CSR (compressed sparse row) and CSC (compressed sparse column), but there are many others.

Some matrices are very sparse. My first real example was the stiffness matrix corresponding to a model of the World Trade Center in New York. The dimension was about 4.5 million, and there was an average of 17 nonzeros per row. Here it was impossible to store the matrix as a dense matrix, but a CSR representation was possible.

EDIT: As for the storage required for the (truncated) SVD it is often convenient to express $A = U\Sigma V^T$ as a sum of rank 1 matrices, i.e. $$ A = \sum_{i=1}^p \sigma_i u_i v_i^T,\quad p = \text{rank $A$},$$ where $u_i \in \mathbb{R}^m$ are the left singular vectors, $v_i \in \mathbb{R}^n$ are the right singular vectors and $\sigma_i > 0$ are the singular values. Each term requires $1 + m + n$ words of storage. If $k$ terms are retained, then the truncated SVD requires $k(m + n + 1)$ words of storage.

$\endgroup$
  • $\begingroup$ Thank you. If we can settle for approximations, and say the discarding threshold is $0.001$. Then for an $m$ * $n$ matrix $A$ = $U$*$S$*$V^t$, suppose there are k singular values that are less than the threshold $0.001$, does it mean that we can use a truncated $U$*$S$*$V^t$ whose dimension is $m*m$, $m * (n-k)$ and $(n-k) * (n-k)$ as an approximation of matrix $A$ if $m \leq n$? $\endgroup$ – Parker Sep 21 '17 at 22:37
  • $\begingroup$ Could you please help me clarify if I am correct? $\endgroup$ – Parker Sep 22 '17 at 0:41
  • $\begingroup$ @Parker. I have added a paragraph in response to your paragraph. $\endgroup$ – Carl Christian Sep 22 '17 at 10:52
  • $\begingroup$ Thank you. Now I get it. $\endgroup$ – Parker Sep 22 '17 at 14:16

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.