  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.
