High dimensional statistics - session 10

This lecture is the tenth session of a course on high-dimensional statistics, taught in Persian. The instructor begins by reviewing the problem of solving an underdetermined linear system Aθ = w, where the goal is to find a unique sparse solution. They recall the concept of sparsity (ℓ0 norm) and the relaxation to ℓ1 minimization. The lecture then focuses on conditions for the ℓ1 relaxation to have a unique solution that matches the sparsest solution. The instructor introduces the tangent cone and the null space of A, and explains that a sufficient condition for uniqueness is that the tangent cone and the null space intersect only at zero. To avoid dependence on the unknown θ, they define the set C_S of perturbations that are more concentrated on the support S, leading to the Restricted Null Space Property (RNSP). They prove a theorem stating that the RNSP is equivalent to the ℓ1 minimization having a unique solution with support S. The proof is detailed, using contradiction and constructing an alternative solution. The lecture then discusses the Mutual Coherence condition as a sufficient condition for the RNSP, and begins to prove that if the mutual coherence is less than 1/(3s), then the RNSP holds for any set S of size s. The proof involves bounding a quadratic form involving A^T A - I. The instructor also mentions applications such as single-pixel cameras and the design of measurement matrices.