Matrix Recipes for Hard Thresholding Methods

Details Matrix Recipes for Hard Thresholding Methods Matrix Recipes for Hard Thresholding Methods

2012-03-20

arxiv.org/abs/1203.4481v1

Computer Science

Information Theory

34 pages

Scientific paper

Given a set of possibly corrupted and incomplete linear measurements, we leverage low-dimensional models to best explain the data for provable solution quality in inversion. A non-exhaustive list of examples includes sparse vector and low-rank matrix approximation. Most of the well-known low dimensional models are inherently non-convex. However, recent approaches prefer convex surrogates that "relax" the problem in order to establish solution uniqueness and stability. In this paper, we tackle the linear inverse problems revolving around low-rank matrices by preserving their non-convex structure. To this end, we present and analyze a new set of sparse and low-rank recovery algorithms within the class of hard thresholding methods. We provide strategies on how to set up these algorithms via basic "ingredients" for different configurations to achieve complexity vs. accuracy tradeoffs. Moreover, we propose acceleration schemes by utilizing memory-based techniques and randomized, $\epsilon$-approximate, low-rank projections to speed-up the convergence as well as decrease the computational costs in the recovery process. For all these cases, we present theoretical analysis that guarantees convergence under mild problem conditions. Simulation results demonstrate notable performance improvements compared to state-of-the-art algorithms both in terms of data reconstruction and computational complexity.

Affiliated with

Also associated with

No associations

Rating

Matrix Recipes for Hard Thresholding Methods 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 Matrix Recipes for Hard Thresholding Methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matrix Recipes for Hard Thresholding Methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-495612