Confusion au sujet du problème de détection compressé

J'ai lu quelques références dont celle-ci .

Je suis un peu confus quel problème d'optimisation compressé détecte les builds et essaie de résoudre. Est-ce

ou et

ou / et autre chose?

Brian est sur place. Mais je pense qu'il est utile d'ajouter un contexte de détection compressé.

Tout d'abord, notez que la soi-disant norme 0 - la fonction de cardinalité, ou le nombre de valeurs non nulles dans x - n'est pas une norme . Il est probablement préférable de l'écrire comme quelque chose comme la carte ( x ) dans tout sauf les contextes les plus décontractés. Ne vous méprenez pas, vous êtes en bonne compagnie lorsque vous utilisez le ‖ x ‖ $\|x\|_0$$x$$\mathop{\textbf{card}}(x)$$\|x\|_0$ raccourci , mais je pense que cela a tendance à semer la confusion.

Les gens savent depuis longtemps que minimiser la norme ‖ x ‖ 1 tend à produire des solutions éparses. Il existe des raisons théoriques à cela liées à la complémentarité linéaire. Mais ce qui était le plus intéressant, ce n'était pas que les solutions étaient rares, mais qu'elles étaient souvent les plus rares possibles . C'est-à-dire que minimiser ‖ x ‖ 1 vous donne vraiment la solution de cardinalité minimale dans certains cas utiles. (Comment ont-ils compris cela, alors que le problème de cardinalité minimale est NP-difficile? En construisant des problèmes artificiels avec des solutions rares connues.) Ce n'était pas quelque chose que la théorie de la complémentarité linéaire pouvait prédire.$\ell_1$$\|x\|_1$$\|x\|_1$

Le domaine de la détection compressée est né lorsque les chercheurs ont commencé à identifier des conditions sur la matrice qui leur permettraient de garantir à l'avance que la solution ℓ 1 était également la plus rare. Voir, par exemple, les premiers articles de Candés, Romberg et Tao , et d'autres discussions sur la propriété d'isométrie restreinte, ou RIP . Un autre site Web utile si vous voulez vraiment plonger dans une théorie est la page de détection compressée de Terence Tao .$A$$\ell_1$

Nous serions ravis de pouvoir résoudre

$\min \| x \|_{0}$

st

$Ax=b$

mais ce problème est un problème d'optimisation combinatoire NP-difficile qui n'est pas pratique à résoudre dans la pratique lorsque , x et b sont de tailles typiques dans la détection en compression. Il est possible de résoudre efficacement$A$$x$$b$

$\min \| x \|_{1}$

st

$Ax=b$

à la fois en théorie (cela peut être fait en temps polynomial) et en pratique informatique pour des problèmes même assez importants qui surviennent dans la détection compressive. Nous utilisons comme "substitut" pour le ‖ x ‖ 0 . Cela a une justification intuitive (la minimisation à une norme préfère les solutions avec moins d'entrées non nulles dans x ), ainsi que des justifications théoriques beaucoup plus sophistiquées (théorèmes de la forme "Si A x = b a une solution k-clairsemée, minimisant alors ‖ x ‖ $\| x \|_{1}$$\| x \|_{0}$$x$$Ax=b$$\| x \|_{1}$ trouvera cette solution avec une forte probabilité « .

$Ax=b$$\| Ax - b \|_{2} \leq \delta$

$\min \| Ax - b\|_{2}^{2} + \lambda \| x \|_{1}$

Je n'ai rien à ajouter aux explications de Brians et Michaels $\ell^1$ contre. $\ell^0$. Mais comme la question semble concerner la détection compressée, j'aimerais ajouter mon point de vue: la détection compressée ne consiste pas à résoudre

Il est possible d'identifier des signaux clairsemés à partir de quelques mesures.

La détection compressée consiste en réalité à prendre le moins de mesures possible pour identifier un signal dans une certaine classe de signaux.

Une phrase accrocheuse est:

Pourquoi votre appareil photo 5 mégapixels devrait-il vraiment mesurer 15 millions de valeurs (trois pour chaque pixel) qui vous coûtent 15 mégaoctets de données alors qu'il ne stocke qu'environ 2 mégaoctets (après compression)?
Serait-il possible de mesurer les 2 mégaoctets tout de suite?

Il existe des cadres assez différents:

• mesures linéaires
• non linéaires (par exemple "sans phase")
• données vectorielles, données matricielles / tensorielles
• la rareté comme juste le nombre de non-zéros
• clarté comme «bas rang» ou même «faible complexité»).

Et il existe également plus de méthodes pour calculer des solutions clairsemées comme les poursuites d'appariement (des variantes comme la poursuite d'appariement orthogonal (OMP), la poursuite d'appariement orthogonal régularisé (ROMP), CoSaMP) ou les méthodes plus récentes basées sur des algorithmes de transmission de messages .

Si l'on identifie la détection comprimée avec de simples $\ell^1$- ou $\ell^0$-minimisation, on manque de beaucoup de flexibilité face à des problèmes pratiques d'acquisition de données.

Cependant, si l'on ne s'intéresse qu'à l'obtention de solutions éparses aux systèmes linéaires, on fait quelque chose que j'appellerais une reconstruction éparse .