Existe-t-il une autre caractérisation de la rareté d'un signal dans la détection compressée

L'hypothèse de départ pour la détection compressée (CS) est que le signal sous-jacent est clairsemé sur une certaine base, par exemple, il y a un maximum de coefficients de Fourier non nuls pour un signal $s$ pars. Et les expériences de la vie réelle montrent que les signaux considérés sont souvent clairsemés.

La question est - étant donné un signal, avant d'envoyer les bits échantillonnés en compression au récepteur et de le laisser récupérer au mieux de ses capacités, existe-t-il un moyen de dire quelle est sa rareté, et s'il s'agit d'un candidat approprié pour compressé sentir en premier lieu?

Sinon, existe-t-il une caractérisation supplémentaire / alternative de la rareté qui peut nous dire rapidement si CS sera utile ou non. On peut voir trivialement que l'expéditeur pourrait faire exactement ce que le récepteur fera avec un ensemble de mesures choisies au hasard, puis essayer de trouver la réponse. Mais existe-t-il un autre moyen de résoudre cette question?

Je soupçonne que quelque chose comme ça doit avoir été étudié, mais je n'ai pas pu trouver un bon pointeur.

Remarque: j'avais posté cette question dans Mathoverflow, il y a quelques semaines, mais je n'ai obtenu aucune réponse. D'où le cross-post.

En effet, il existe des moyens d'estimer la rareté ou le contenu de l'information au niveau du dispositif d'acquisition. Les détails, le caractère pratique et l'utilité réelle de le faire peuvent être discutés et dépendent fortement du contexte dans lequel il est appliqué. Dans le cas de l'imagerie, on pourrait déterminer des zones d'une image qui sont plus ou moins compressibles sur une base prédéterminée. Par exemple, voir «Échantillonnage compressif basé sur la saillance pour les signaux d'image» de Yu et al . Dans ce cas, les exigences de complexité supplémentaires imposées au dispositif d'acquisition fournissent des gains marginaux.

En ce qui concerne vos questions concernant la détermination de l'utilité de la compression compressée sur un signal donné au moment de l'acquisition: si le signal en question adhère à tout type de modèle connu a priori , la compression compressée est possible. Une récupération précise dépend simplement du rapport entre le nombre de mesures prises et le degré d'adhérence du signal échantillonné à votre modèle. Si c'est un mauvais modèle, vous ne dépasserez pas la transition de phase. S'il s'agit d'un bon modèle, vous pourrez alors calculer une reconstruction précise du signal d'origine. De plus, les mesures de détection comprimée sont, en général, pérennes. Si vous avez un nombre donné de mesures pour un signal qui est insuffisant pour récupérer avec précision le signal d'origine en utilisant le modèle que vous avez aujourd'hui, alors il est toujours possible de concevoir demain un meilleur modèle pour lequel ces mesures sont suffisantes pour une récupération précise.

Note supplémentaire (modifier): L'approche d'acquisition mentionnée dans votre question sonnait assez proche de la détection compressive adaptative, j'ai donc pensé que ce qui suit pourrait intéresser les lecteurs de cette question. Les résultats récents d'Arias-Castro, Candes et Davenport ont montré que les stratégies de mesure adaptative ne peuvent, en théorie, offrir aucun gain significatif par rapport à la détection comprimée non adaptative (c'est-à-dire aveugle). Je renvoie les lecteurs à leur travail, "Sur les limites fondamentales de la détection adaptative", qui devrait bientôt paraître dans l'ITIT.

Une approche pratique serait de vérifier votre signal d'intérêt avec une sélection de dictionnaires pour déterminer s'il est rare dans l'un d'eux. Vous n'avez pas réellement à faire ce que le récepteur ferait, c'est-à-dire compresser et reconstruire le signal, pour voir s'il est rare dans le dictionnaire particulier. Vous pouvez lui appliquer une transformation linéaire et vérifier si le vecteur transformé est rare. Si c'est le cas, la transformation inverse est votre dictionnaire. Par clarté, je veux dire compter le nombre de coefficients non nuls ou non négligeables dans le vecteur. Par exemple, calculez la DFT de votre signal. Si sa représentation dans le domaine fréquentiel s'avère clairsemée (suffisante), vous pouvez utiliser la DFT inverse comme dictionnaire. Si la transformation n'est pas inversible, par exemple une matrice large, elle n'est pas aussi simple, mais elle devrait quand même être réalisable avec des trames.

Concernant les alternatives à la rareté, endolith mentionne quelques tentatives de généraliser la "simplicité" à plus que la simple rareté. De plus, il y a aussi:

1. Rang bas: utilisé dans l'achèvement de la matrice, qui est une sorte de généralisation matricielle de la détection compressée. Voir par exemple la complétion exacte de la matrice via l'optimisation convexe et les nouveaux articles de Candès et al.
2. " k -simpleness": les vecteurs ne sont pas exactement clairsemés; la plupart de leurs entrées sont soit a ou b et quelques ( k ) d'entre elles sont entre les deux. Ceci est par exemple décrit dans Donoho & Tanner, «Precise Undersampling Theorems» (exemple 3).

$\|x\|_1^2/\|x\|_2^2$