Analysis of sparse representations using bi-orthogonal dictionaries

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 l₁-norm of x under the constraint y = Dx. In this paper, the performance of l₁-reconstruction is analyzed, when the dictionary is bi-orthogonal D = [O₁ O₂], where O₁, O₂ 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₁-recovery is possible with bi-orthogonal dictionaries.