On uniqueness of sparse signal recovery

A basic issue of sparse signal recovery (SSR) is to explore the condition of the uniqueness with regard to the solution of the relevant optimization framework. However, the standard uniqueness conditions, such as spark condition, NSP (null space property), RIP (restricted isometry property) and mutual coherence condition, are with respect to any sparse signal with the same sparsity. Therefore, these four conditions require certain structural or metric properties of all possible sub-matrices from the measurement matrix corresponding to the possible support indices and are quite restrictive for a given sparse signal with its support indices fixed. This work mainly considers the uniqueness issue of SSR. With the extra information of the support indices, the requirements of the measurement matrix for guaranteeing the uniqueness are released. Theoretical analysis has been performed on the uniqueness for l0-norm and l1-norm frameworks, in which loosed conditions are further validated by constructed examples. These discoveries can explain the phenomena that the occasional success of SSR in numerical simulation occurs when the above four conditions cannot be satisfied. Besides, it is analyzed that the spark condition and NSP condition are the minimal requirements for the unique recovery of the standard l0-norm framework and the l1-norm framework respectively.