Near-Optimal Column-Based Matrix Reconstruction

Details Near-Optimal Column-Based Matrix Reconstruction Near-Optimal Column-Based Matrix Reconstruction

2011-03-04

arxiv.org/abs/1103.0995v2

Computer Science

Data Structures and Algorithms

27 pages

Scientific paper

We consider low-rank reconstruction of a matrix using its columns and we present asymptotically optimal algorithms for both spectral norm and Frobenius norm reconstruction. The main tools we introduce to obtain our r esults are: (i) the use of fast approximate SVD-like decompositions for column reconstruction, and (ii) two deter ministic algorithms for selecting rows from matrices with orthonormal columns, building upon the sparse represen tation theorem for decompositions of the identity that appeared in \cite{BSS09}.

Affiliated with

Also associated with

No associations

Rating

Near-Optimal Column-Based 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 Near-Optimal Column-Based Matrix Reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Near-Optimal Column-Based Matrix Reconstruction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8564