2012/12/22 by Yun-Bin Zhao, Zhao, Yun-Bin
Engineering · #15A06 #15A29 #65K10 #94A12 #Advanced Fiber Optic Sensors #FOS: Mathematics #Microwave Imaging and Scattering Analysis #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1212.5682
openalex publication_date 2012/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.