Theorem 2.1. For an arbitrary pair of orthogonal basesΨ,Φwith mutual-coherenceμ(A), and for an arbitrary non-zero vector b∈IRⁿ with representationsαandβcorrespondingly,the following inequality holds true:

Uncertainty Principle 1 :  

Theorem 2.2. Any two distinct solutions x1; x2 of the linear system [Ψ;Φ]x = b

cannot both be very sparse, governed by the following uncertainty principle:

Uncertainty Principle 2 :     

We refer to this result as an uncertainty of redundant solutions, as we discuss here solutions to the underdetermined system.

(1) via SparkF

(2) via Mutual-Coherence

If

is empty, we can get the 1 norm get the same result as 0 norm, and it’s the sparsest solution.

Prove that: