High dimensional statistics - session 10

Cette session de cours en statistiques haute dimension se concentre sur les conditions garantissant l’unicité de la solution du problème de minimisation de la norme L1 sous contraintes linéaires (relaxation du problème de minimisation de la norme L0). Le professeur commence par rappeler le cadre : résoudre un système linéaire sous-déterminé Aθ = y, où θ est supposé sparse. La relaxation L1 est utilisée car la minimisation L0 est combinatoire. La question centrale est de savoir quand la solution L1 est unique et coïncide avec la solution L0. Le concept de ’tangent cone’ est introduit, puis généralisé en ‘set C_S’ pour éviter la dépendance à θ. La ‘restricted null space property’ (RNSP) est définie comme l’intersection vide entre C_S et le noyau de A (hors zéro). Un théorème d’équivalence est démontré : la RNSP est équivalente à l’unicité de la solution L1 pour tout θ de support S. La preuve est détaillée dans les deux sens. Ensuite, une condition suffisante plus facile à vérifier est présentée : la ‘mutual coherence’ de la matrice A, qui borne les corrélations entre colonnes. Si la cohérence est inférieure à 1/(3s), alors la RNSP est satisfaite. La session se termine par une discussion sur la construction de matrices aléatoires (par exemple, distribution de Rademacher) pour garantir la propriété, et mentionne le compressed sensing comme application.