Optimization Online


New and Improved Conditions for Uniqueness of Sparsest Solutions of Underdetermined Linear Systems

Y Zhao(y.zhao.2***at***bham.ac.uk)

Abstract: The uniqueness of sparsest solutions of underdetermined linear systems plays a fundamental role in the newly developed compressed sensing theory. Several new algebraic concepts, including the sub-mutual coherence, scaled mutual coherence, coherence rank, and sub-coherence rank, are introduced in this paper in order to develop new and improved sufficient conditions for the uniqueness of sparsest solutions. The coherence rank of a matrix with normalized columns is the maximum number of absolute entries in a row of its Gram matrix that are equal to the mutual coherence. The main result of this paper claims that when the coherence rank of a matrix is low, the mutual-coherence-based uniqueness conditions for the sparsest solution of a linear system can be improved. Furthermore, we prove that the Babel-function-based uniqueness can be also improved by the so-called sub-Babel function. Moreover, we show that the scaled-coherence-based uniqueness conditions can be developed, and that the right-hand-side vector $b$ of a linear system, the support overlap of solutions, the orthogonal matrix out of the singular value decomposition of a matrix, and the range property of a transposed matrix can be also integrated into the criteria for the uniqueness of the sparsest solution of an underdetermined linear system.

Keywords: Sparsest solution, underdetermined linear system, spark, (sub-)mutual coherence, coherence rank, range property.

Category 1: Global Optimization

Category 2: Combinatorial Optimization

Category 3: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 05/31/2013
Entry Accepted: 05/31/2013
Entry Last Modified: 05/31/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society