Optimal Column-Based Low-Rank Matrix Reconstruction

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

8 pages

Scientific paper

We prove that for any real-valued matrix $X \in \R^{m \times n}$, and positive integers $r \ge k$, there is a subset of $r$ columns of $X$ such that projecting $X$ onto their span gives a $\sqrt{\frac{r+1}{r-k+1}}$-approximation to best rank-$k$ approximation of $X$ in Frobenius norm. We show that the trade-off we achieve between the number of columns and the approximation ratio is optimal up to lower order terms. Furthermore, there is a deterministic algorithm to find such a subset of columns that runs in $O(r n m^{\omega} \log m)$ arithmetic operations where $\omega$ is the exponent of matrix multiplication. We also give a faster randomized algorithm that runs in $O(r n m^2)$ arithmetic operations.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Optimal Column-Based Low-Rank Matrix Reconstruction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Column-Based Low-Rank Matrix Reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Column-Based Low-Rank Matrix Reconstruction will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-353532

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.