Analogues de la détection compressée

$x \in \mathbb{R}^n$$\|x\|_0 < k$$Ax$$A$$R$$n$ matrice réelle où nous voulons . La magie de la détection compressée est que l'on peut explicitement construire telle sorte qu'il permet une récupération exacte rapide (temps quasi-linéaire) de tout$R \ll n$$A$$k$-sparse $x$ avec $R$ aussi petit que $O(k n^{o(1)})$ . Je n'ai peut-être pas les paramètres les plus connus, mais c'est l'idée générale.

Ma question est: existe-t-il des phénomènes similaires dans d'autres contextes? Ce que je veux dire, c'est que le signal d'entrée pourrait provenir d'une "famille de faible complexité" selon une mesure de complexité qui n'est pas nécessairement clairsemée. Nous voulons alors des algorithmes de compression et de décompression, pas nécessairement des cartes linéaires, efficaces et corrects. Ces résultats sont-ils connus dans un contexte différent? Quelle serait votre supposition pour une théorie plus «générale» de la détection compressée?

(Bien sûr, dans les applications de détection compressée, la linéarité et la rareté sont des questions importantes. La question que je pose ici est plus "philosophique".)

Votre question porte sur le problème de récupération "exact" (nous voulons récupérer un k-sparse $x$exactement donné $Ax$ ). Dans ce qui suit, je me concentrerai sur la version "robuste", où $x$ est un vecteur arbitraire et le but de l'algorithme de récupération est de trouver une approximation $k$ parsée $x'$ à $x$ (cette distinction importe en fait pour une partie de la discussion ci-dessous ). Formellement, vous voulez suivre le problème (appelez-le $P_1$ ):

Conception $A$ telle que pour tout $x$ on puisse récupérer $x'$ où $\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$ , où$x"$ s'étend sur tous lesvecteurs$k$ -pars.

Ici, $\| \cdot \|_L$ et désigne la norme gauche et la droite, et ℓ $\| \cdot \|_R$$C$ est le "facteur d'approximation". Il existe différents choix possibles pour et ‖ ⋅ ‖ R . Pour le concret, on peut penser que les deux sont égaux à ℓ 2 ou ; cela peut devenir plus salissant cependant.$\| \cdot \|_L$$\| \cdot \|_R$$\ell_2$$\ell_1$

Passons maintenant à certains des analogies et des généralisations.

Base arbitraire. Tout d'abord, notez que tout schéma satisfaisant à la définition ci-dessus peut être utilisé pour résoudre un problème plus général, où le signal récupéré $x'$ est rare sur une base arbitraire (disons, ondelette de Fourier), pas seulement le standard. Soit la matrice de base. Formellement, un vecteur u est k- sparse dans la base B si u = B v où v est k- sparse. Nous pouvons maintenant considérer le problème généralisé (appelons-le P $B$$u$$k$$B$$u=Bv$$v$$k$$P_B$ ):

Conception telle que, étant donné A B x , on peut récupérer x ′ où ‖ x - x ′ ‖ L$A_B$$A_B x$$x'$$\|x-x'\|_L \le$

, où x " s'étend sur tous les vecteurs qui sont k -sparse dans$\min_{x"} C \|x-x"\|_R$$x"$$k$$B$ .

On peut réduire ce problème au problème précédent en changeant la base, c'est-à-dire en utilisant une matrice de mesure A B = A B - 1 . Si nous avons une solution à P 1 dans le$P_1$$A_B = A B^{-1}$$P_1$norme ℓ 2 (c'est-à-dire, les normes gauche et droite égales à ℓ 2 ), nous obtenons également une solution à P B dans lanorme ℓ 2 . Si P 1 utilise d'autres normes, nous résolvons P B dans ces normes modifiées en changeant la base.$\ell_2$$\ell_2$$P_B$$\ell_2$$P_1$$P_B$

Une mise en garde en ce qui précède est que l'approche ci - dessus, nous avons besoin de connaître la matrice afin de définir A B . Peut-être surprenant, si nous permettons à Aléa ( A B est pas fixe mais au lieu choisi au hasard), il est possible de choisir un B de la distribution fixe qui est indépendante de B . Il s'agit de la propriété dite d' universalité .$B$$A_B$$A_B$$A_B$$B$

Dictionnaires. La généralisation suivante peut être obtenue en supprimant l'exigence selon laquelle est une base. Au lieu de cela, nous pouvons autoriser B à avoir plus de lignes que de colonnes. Ces matrices sont appelées dictionnaires (trop complets). Un exemple populaire est la matrice d'identité au-dessus de la matrice de Fourier. Un autre exemple est une matrice où les lignes sont les vecteurs caractéristiques de tous les intervalles dans {1 ... n}; dans ce cas, l'ensemble { B u : u est k-sparse } contient tous les " k -histogrammes", c'est-à-dire des fonctions constantes par morceaux sur {1 ... n} avec au plus $B$$B$$Bu: \mbox{u is k-sparse}$$k$$k$ pièces.

Pour autant que je sache, il n'existe pas de théorie générale pour de tels dictionnaires arbitraires, bien qu'il y ait eu pas mal de travail sur ce sujet. Voir, par exemple, Candes-Eldar-Needell'10 ou Donoho-Elad-Temlyakov, IEEE Transactions on Information Theory, 2004 .

L'esquisse d'histogrammes a été largement étudiée dans la littérature en streaming et dans les bases de données, par exemple, Gilbert-Guha-Indyk-Kotidis-Muthukrishnan-Strauss, STOC 2002 ou Thaper-Guha-Indyk-Koudas, SIGMOD 2002 .

Des modèles. (également mentionné par Arnab). Une généralisation différente consiste à introduire des restrictions sur les modèles de rareté. Soit un sous-ensemble de k sous-ensembles de {1 ... n}. Nous disons que u est M -sparse si le support de u est inclus dans un élément de M . Nous pouvons maintenant poser le problème (appelons-le P M ):$M$$k$$u$$M$$u$$M$$P_M$

Conception telle que pour tout x on puisse récupérer x ′ où ‖ x - x ′ ‖ L$A$$x$$x'$$\|x-x'\|_L \le$

, où x " s'étend sur tous lesvecteurs M -pars.$\min_{x"} C \|x-x"\|_R$$x"$$M$

Par exemple, les éléments de pourraient être de la forme I 1$M$ , où chaque I i correspond à un "sous-bloc" de {1 ... n} d'une certaine longueur b , c'est-à-dire que I i est de la forme {jb + 1 ... (j + 1) b} pour certains j . Il s'agit du modèle dit "à faible densité de blocs". $I_1 \cup \ldots \cup I_k$$I_i$$b$$I_i$$j$

Les avantages des modèles sont que l'on peut économiser sur le nombre de mesures, par rapport à l' approche générique de parité. Cela est dû au fait que l'espace des signaux M- sparse est plus petit que l'espace de tous les signaux k- sparse, donc la matrice A doit conserver moins d'informations. Pour plus d'informations, voir Baraniuk-Cevher-Duarte-Hegde, IEEE Transactions on Information Theory, 2010 ou $k$$M$$k$$A$ Eldar-Mishali, IEEE Transactions on Information Theory, 2009 .

J'espère que cela t'aides.

Il y a une généralisation de la détection compressée au paramètre non commutatif appelé complétion de matrice . Dans le cadre exact, vous avez un inconnu matrice M qui, au lieu de parcimonie, est connu pour avoir un faible rang r « m , n . Votre objectif est de reconstruire les r valeurs singulières et les vecteurs singuliers de cette matrice en échantillonnant uniquement ˜ $m \times n$$M$$r \ll m,n$$r$ coefficients de la matrice, plutôt que O ( m n ) comme requis dans le pire des cas. $\tilde{O}(rm+rn)$$O(mn)$

Si les vecteurs singuliers sont suffisamment "incohérents" (à peu près, pas trop bien alignés) avec la base sur laquelle vous échantillonnez les éléments de matrice, alors vous pouvez réussir avec une forte probabilité en résolvant un programme convexe, similaire à la détection compressée standard. Dans ce cas, vous devez minimiser la norme Schatten 1, c'est-à-dire la somme des valeurs singulières.

Ce problème a également de nombreuses applications, par exemple, pour donner des recommandations de livre à un client d'une librairie en ligne en ne connaissant que les quelques évaluations que d'autres clients ont générées. Dans ce contexte, les lignes et les colonnes de sont étiquetées respectivement par les livres et les clients. Les quelques éléments de matrice visibles sont les évaluations des clients des livres qu'ils ont précédemment achetés. La matrice M devrait être de faible rang, car nous pensons que seuls quelques facteurs principaux influencent nos préférences. En remplissant $M$$M$$M$ , le vendeur peut faire des prédictions précises sur les livres que vous voudrez probablement.

Un bon début est cet article de Candés et Recht, Exact Matrix Completion via Convex Optimization . Il y a aussi une généralisation vraiment cool où vous êtes autorisé à échantillonner de manière arbitraire pour l'espace matriciel. Cet article de David Gross, Récupération des matrices de bas rang à partir de quelques coefficients dans n'importe quelle base utilise cette généralisation pour simplifier considérablement les preuves de complétion de la matrice, et pour certaines bases, vous pouvez également supprimer l'hypothèse d'incohérence. Cet article contient également les meilleures limites à ce jour sur la complexité de l'échantillonnage. Cela peut sembler étrange d'échantillonner de manière arbitraire, mais c'est en fait assez naturel dans le cadre de la mécanique quantique, voir par exemple cet article, Tomographie d'état quantique via la détection compressée .

Il existe une détection compressée basée sur une variété, dans laquelle la condition de rareté est remplacée par la condition que les données se trouvent sur un sous-collecteur de faible dimension de l'espace naturel des signaux. Notez que la rareté peut être exprimée comme reposant sur une variété particulière (en fait, une variété sécante).

Voir, par exemple ce document et les références dans son introduction. (Certes, je ne sais pas si cet article est représentatif de la région - je connais mieux le sujet connexe des classificateurs à base multiple à la Niyogi-Smale-Weinberger .)

Je suppose que, au niveau de généralité dans lequel j'ai posé la question, l'article "Compression des sources échantillonnables" de Trevisan, Vadhan et Zuckerman (2004) constitue également une réponse possible. Ils montrent que dans de nombreux cas, si la source des chaînes d'entrée est de faible complexité (par exemple, échantillonnable par les machines de l'espace de journalisation), alors on peut compresser et décompresser, en temps polynomial pour allonger une constante additive loin de l'entropie de la source.

Je ne sais pas vraiment si la détection compressée peut être intégrée dans une théorie plus large de la compression.

Un analogue de la détection compressive est dans l'apprentissage automatique lorsque vous essayez d'estimer un vecteur de poids dimensionnel élevé (par exemple, en classification / régression) à partir d'un très petit échantillon. Pour faire face à des systèmes sous-déterminés d'équations linéaires dans de tels paramètres, on applique généralement une rareté (via une pénalité de l0 ou l1) sur le vecteur de poids en cours d'apprentissage. Pour voir la connexion, considérez le problème de classification / régression suivant de l'apprentissage automatique:

Représenter les N exemples de dimensions D chacun (D >> N) comme une matrice NxD X. Représenter les N réponses (une pour chaque exemple) comme un vecteur Nx1 Y. Le but est de résoudre pour un vecteur Dx1 thêta via l'équation suivante : Y = X * thêta

Voici maintenant l'analogie de ce problème avec la détection compressive (CS): vous voulez estimer / mesurer le thêta qui est un vecteur dimensionnel D (semblable à un "signal" inconnu dans CS). Pour estimer cela, vous utilisez une matrice X (semblable à la matrice de conception dans CS) et N mesures 1-D Y (semblable au signal compressé dans CS, depuis D >> N).

Voir: http://www.damtp.cam.ac.uk/user/na/people/Anders/Inf_CS43.pdf