Analysis of Basis Pursuit Via Capacity Sets

Details Analysis of Basis Pursuit Via Capacity Sets Analysis of Basis Pursuit Via Capacity Sets

2010-04-25

arxiv.org/abs/1004.4329v1

Journal of Fourier Analysis and Applications, Volume 14, Numbers 5-6, December 2008, pp. 688-711

Computer Science

Numerical Analysis

Scientific paper

10.1007/s00041-008-9036-y

Finding the sparsest solution $\alpha$ for an under-determined linear system of equations $D\alpha=s$ is of interest in many applications. This problem is known to be NP-hard. Recent work studied conditions on the support size of $\alpha$ that allow its recovery using L1-minimization, via the Basis Pursuit algorithm. These conditions are often relying on a scalar property of $D$ called the mutual-coherence. In this work we introduce an alternative set of features of an arbitrarily given $D$, called the "capacity sets". We show how those could be used to analyze the performance of the basis pursuit, leading to improved bounds and predictions of performance. Both theoretical and numerical methods are presented, all using the capacity values, and shown to lead to improved assessments of the basis pursuit success in finding the sparest solution of $D\alpha=s$.

Affiliated with

Also associated with

No associations

Rating

Analysis of Basis Pursuit Via Capacity Sets 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 Analysis of Basis Pursuit Via Capacity Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of Basis Pursuit Via Capacity Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-186369