Gibt es eine alternative Charakterisierung der Sparsamkeit eines Signals bei der komprimierten Erfassung?

Die Ausgangsannahme für die komprimierte Erfassung (Compressed Sensing, CS) ist, dass das zugrunde liegende Signal in gewisser Weise dünn ist, z. B. gibt es ein Maximum von Fourier-Koeffizienten ungleich Null für ein sparsames Signal. Und reale Erfahrungen zeigen, dass die untersuchten Signale oft spärlich sind.$s$

Die Frage ist, ob ein Signal gegeben wird, bevor die komprimiert abgetasteten Bits an den Empfänger gesendet werden und sie sich nach besten Kräften erholen kann, ob es sich um einen geeigneten Kandidaten für die Komprimierung handelt überhaupt spüren?

Alternativ gibt es eine zusätzliche / alternative Charakterisierung von Sparsity, die uns schnell sagen kann, ob CS nützlich sein wird oder nicht. Man kann trivialerweise sehen, dass der Sender genau das tun kann, was der Empfänger mit einer zufällig ausgewählten Menge von Messungen tun wird, und dann versuchen, die Antwort herauszufinden. Aber gibt es eine alternative Möglichkeit, diese Frage zu lösen?

Mein Verdacht ist, dass so etwas studiert worden sein muss, aber ich konnte keinen guten Zeiger finden.

Hinweis: Ich hatte diese Frage vor ein paar Wochen in Mathoverflow gepostet, aber keine Antwort erhalten. Daher der Cross-Post.

In der Tat gibt es Möglichkeiten, wie die Sparsamkeit oder der Informationsgehalt am Erfassungsgerät geschätzt werden können. Die Details, die Praktikabilität und der tatsächliche Nutzen dieses Vorgehens sind umstritten und hängen stark vom Kontext ab, in dem es angewendet wird. Im Falle der Bildgebung könnte man Bereiche eines Bildes bestimmen, die auf einer vorbestimmten Basis mehr oder weniger komprimierbar sind. Siehe zum Beispiel "Saliency-Based Compressive Sampling for Image Signals" von Yu et al . In diesem Fall sorgen die zusätzlichen Komplexitätsanforderungen an das Erfassungsgerät für marginale Gewinne.

In Bezug auf Ihre Fragen zur Bestimmung des Nutzens von Compressed Sensing für ein bestimmtes Signal zum Zeitpunkt der Erfassung: Wenn das betreffende Signal einem a priori bekannten Modell entspricht , ist Compressed Sensing möglich. Die genaue Wiederherstellung hängt einfach vom Verhältnis zwischen der Anzahl der durchgeführten Messungen und dem Grad ab, bis zu dem das abgetastete Signal Ihrem Modell entspricht. Wenn es ein schlechtes Modell ist, kommen Sie nicht über den Phasenübergang hinaus. Wenn es sich um ein gutes Modell handelt, können Sie eine genaue Rekonstruktion des ursprünglichen Signals berechnen. Darüber hinaus sind Compressed Sensing-Messungen im Allgemeinen zukunftssicher. Wenn Sie eine bestimmte Anzahl von Messungen für ein Signal haben, deren Anzahl nicht ausreicht, um das ursprüngliche Signal mit dem Modell, über das Sie heute verfügen, genau wiederherzustellen, können Sie auch morgen ein besseres Modell entwickeln, für das diese Messungen für eine genaue Wiederherstellung ausreichen.

Zusätzlicher Hinweis (Bearbeiten): Der in Ihrer Frage erwähnte Akquisitionsansatz kam dem adaptiven Compressed Sensing sehr nahe, daher dachte ich, dass das Folgende für die Leser dieser Frage von Interesse sein könnte. Jüngste Ergebnisse von Arias-Castro, Candes und Davenport haben gezeigt, dass adaptive Messstrategien theoretisch keine signifikanten Vorteile gegenüber nicht adaptiver (dh blinder) komprimierter Abtastung bieten können. Ich verweise die Leser auf ihre Arbeit "Über die grundlegenden Grenzen des adaptiven Erfassens", die bald im ITIT erscheinen sollte.

Ein praktischer Ansatz wäre es, Ihr Signal von Interesse mit einer Auswahl von Wörterbüchern zu überprüfen, um herauszufinden, ob es in einem dieser Wörterbücher spärlich ist. Sie müssen eigentlich nicht das tun, was der Empfänger tun würde, dh das Signal komprimieren und rekonstruieren, um festzustellen, ob es in dem bestimmten Wörterbuch spärlich ist. Sie können eine lineare Transformation darauf anwenden und prüfen, ob der transformierte Vektor dünn ist. Wenn dies der Fall ist, ist die inverse Transformation Ihr Wörterbuch. Mit "dünn" meine ich die Anzahl der Koeffizienten ungleich Null oder nicht vernachlässigbar im Vektor. Berechnen Sie zum Beispiel die DFT Ihres Signals. Wenn sich herausstellt, dass die Frequenzdomänendarstellung spärlich genug ist, können Sie die inverse DFT als Wörterbuch verwenden. Wenn die Transformation nicht invertierbar ist, z. B. eine breite Matrix, ist sie nicht ganz so einfach, sollte aber dennoch mit Frames möglich sein.

In Bezug auf Alternativen zu Sparsity erwähnt Endolith einige Versuche, die "Einfachheit" auf mehr als nur Sparsity zu verallgemeinern. Darüber hinaus gibt es auch:

1. Niedriger Rang: Wird bei der Matrixvervollständigung verwendet, bei der es sich um eine Art Matrixverallgemeinerung der komprimierten Erfassung handelt. Siehe zum Beispiel Exakte Matrixvervollständigung durch konvexe Optimierung und neuere Arbeiten von Candès et al.
2. " k- Einfachheit": die Vektoren sind nicht gerade dünn; Die meisten Einträge sind entweder a oder b und einige ( k ) dazwischen. Dies ist beispielsweise in Donoho & Tanner, 'Precise Undersampling Theorems' (Beispiel 3) beschrieben.

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