On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing

Details On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing

2010-01-28

arxiv.org/abs/1001.5103v2

Mathematics

Optimization and Control

Scientific paper

We consider the synthesis problem of Compressed Sensing - given s and an MXn matrix A, extract from it an mXn submatrix A', certified to be s-good, with m as small as possible. Starting from the verifiable sufficient conditions of s-goodness, we express the synthesis problem as the problem of approximating a given matrix by a matrix of specified low rank in the uniform norm. We propose randomized algorithms for efficient construction of rank k approximation of matrices of size mXn achieving accuracy bounds O(1)sqrt({ln(mn)/k) which hold in expectation or with high probability. We also supply derandomized versions of the approximation algorithms which does not require random sampling of matrices and attains the same accuracy bounds. We further demonstrate that our algorithms are optimal up to the logarithmic in m and n factor. We provide preliminary numerical results on the performance of our algorithms for the synthesis problem.

Affiliated with

Also associated with

No associations

Rating

On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing 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 On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-254235