Relation de la compression compressée avec la régularisation L1

Je comprends que la détection compressée trouve la solution la plus simple à

y = A x

$y = Ax$ où

x \in R^{D}

$x \in \mathbb{R}^D$ ,

A \in R^{k \times D}

$A \in \mathbb{R}^{k \times D}$ , et

y \in R^{k}

$y \in \mathbb{R}^{k}$ ,

k << D

$k << D$ .

De cette façon, nous pouvons reconstruire $x$ (l'original) en utilisant $y$ (la compression), assez rapide. Nous disons que $x$ est la solution la plus clairsemée. La rareté peut être comprise comme $l_0$ -norm pour les vecteurs.

Nous savons également que $l_1$ -norm (résoluble en utilisant une programmation linéaire) est une bonne approximation de la $l_0$ -norm (qui est NP-difficile pour les grands vecteurs). Donc $x$ est aussi le plus petit $l_1$ solution à $Ax=y$

J'ai lu que la détection compressée est similaire à la régression avec une pénalité au lasso ( $l_1$ ). J'ai également vu des interprétations géométriques de cela, mais je n'ai pas fait le lien mathématiquement.

Autre que de minimiser $l_1$ norme, quelle est la relation (mathématique) entre la compression et le lasso?

lasso sparse ilanman
la source

en relation: quora.com/…

Charlie Parker

à ma connaissance, la détection comprimée est le domaine qui étudie la récupération des signaux clairsemés et la régularisation L1 n'est qu'une formulation spécifique pour la résoudre approximativement.

Charlie Parker

Il n'y a essentiellement aucune différence. C'est juste la terminologie du statisticien vs la terminologie de l'ingénieur électrique.

La détection compressée (plus précisément, le débruitage de poursuite de base [1]) est ce problème:

$\text{arg min}_x \frac{1}{2}\|Ax - b\| + \lambda \|x\|_1$

tandis que le Lasso [2] est ce problème

$\text{arg min}_{\beta} \frac{1}{2}\|y - X\beta\| + \lambda \|\beta\|_1$

Dans la mesure où il y a une différence, c'est que dans les applications de détection compressée, vous (l'ingénieur) pouvez choisir pour être "bien comporté" tandis que, pour le Lasso, vous (le statisticien) ne pouvez pas choisir et devez traiter quelles que soient les données (et elles sont rarement "sympas" ...). Par conséquent, une grande partie de la littérature ultérieure sur la détection comprimée s'est concentrée sur le choix de pour être aussi "efficace" que possible, tandis qu'une grande partie de la littérature statistique ultérieure s'est concentrée sur les améliorations du lasso qui fonctionnent toujours avec qui "cassent" le lasso. $A$ $X$ $A$ $X$

[1] SS Chen, DL Donoho, MA Saunders. "Décomposition atomique par poursuite de base." SIAM Journal on Scientific Computing 20 (1), p.33-61, 1998. https://doi.org/10.1137/S1064827596304010

[2] R. Tibshirani "Rétrécissement et sélection de la régression via le lasso". Journal de la Royal Statistical Society: série B 58 (1), p.267–88, 1996. JSTOR 2346178.

mweylandt
la source

mais la détection généralement compressée est formulée comme tel que . Est-ce vraiment équivalent à min de si oui, pourquoi et comment lambda apparaît-il dans l'image d'origine?

m i n ‖ x ‖_{1}

$min \| x \|_1$

A x = b

$Ax=b$

‖ A x - b ‖ + λ ‖ x ‖_{1}

$\|Ax - b \| + \lambda \| x \|_1$

Charlie Parker

La formulation que vous donnez (avec la contrainte d'égalité) est la «limite» dans un sens comme . Elle survient lorsque vous supposez qu'il n'y a pas de bruit dans le système (c'est ce qu'on appelle souvent «poursuite de base» par opposition à «débruitage de poursuite de base»).

λ \to 0

$\lambda \to 0$

mweylandt

quelque chose que je suis confus, c'est que je fais correspondre les méthodes de poursuite où les algorithmes gourmands pour résoudre (approximativement) . Cependant, je pensais que les algorithmes de seuillage doux où les solveurs exacts à la formulation de relaxation convexe . Ainsi, si cela est vrai, conduiraient-ils à la même solution? c'est-à-dire qu'il semble que Lasso et OM résolvent le même problème mais avec une formulation très différente. N'importe quel algorithme pour LASSO donne la même solution parce que son convexe si OM est un algorithme gourmand pour L0, alors je suppose qu'ils sont très différents. Est-ce correct?

‖ X w - y ‖^{2} + λ ‖ w ‖_{0}

$\| Xw - y \|^2 + \lambda \| w \|_0$

‖ X w - y ‖^{2} + λ ‖ w ‖_{1}

$\| Xw - y \|^2 + \lambda \| w \|_1$

Charlie Parker

Je pense que cela vaut la peine d'être posé dans une question distincte. En général, non - les solutions L1 (lasso) et L0 (meilleurs sous-ensembles) sont différentes. Mais il existe des circonstances bien étudiées particulières où les versions L0 et L1 du problème de poursuite de base (et non le bruit de poursuite de base) donnent la même solution.

mweylandt

Voici l'autre question: stats.stackexchange.com/questions/337113/…

Charlie Parker

Relation de la compression compressée avec la régularisation L1

Réponses: