62-07 Data analysis
Refine
Year of publication
- 2008 (1)
Language
- English (1)
Keywords
- $CUR$ decomposition (1)
- Tucker decomposition (1)
- approximation (1)
- least squares (1)
- rank $k$ (1)
- singular value decomposition (1)
Project
- A9 (1)
Application Area
- A (1)
In many applications such as data compression, imaging or
genomic data analysis,
it is important to approximate a given $m\times n$ matrix $A$
by a matrix $B$ of rank at most $k$ which is much smaller than $m$ and $n$.
The best rank $k$ approximation can be determined via
the singular value decomposition
which, however, has prohibitively
high computational complexity and storage requirements
for very large $m$ and $n$.
We present an optimal least squares algorithm for computing a rank $k$
approximation to an $m\times n$ matrix $A$ by reading
only a limited number of rows and columns of $A$.
The algorithm has complexity $\mathcal O(k^2\max(m,n))$ and
allows to iteratively improve given rank $k$
approximations by reading additional rows and
columns of $A$. We also show how this approach can be extended
to tensors and present numerical results.