Search

The sparse representation problem of recovering an N dimensional sparse vector x from M < N linear observations y = Dx given dictionary D is considered. The standard approach is to let the elements of the dictionary be independent and identically distributed (IID) zero-mean Gaussian and minimize the l1-norm of x under the constraint y = Dx. In this paper, the performance of l1-reconstruction is analyzed, when the dictionary is bi-orthogonal D = [O1 O2], where O1, O 2 are independent and drawn uniformly according to the Haar measure on the group of orthogonal M × M matrices. By an application of the replica method, we obtain the critical conditions under which perfect l 1-recovery is possible with bi-orthogonal dictionaries., QC 20130219

Reconstruction fidelity of sparse signals contaminated by sparse noise is considered. Statistical mechanics inspired tools are used to show that the l(1)-norm based convex optimization algorithm exhibits a phase transition between the possibility of perfect and imperfect reconstruction. Conditions characterizing this threshold are derived and the mean square error of the estimate is obtained for the case when perfect reconstruction is not possible. Detailed calculations are provided to expose the mathematical tools to a wide audience., QC 20140625