Support Recovery in One-bit Compressed Sensing with Near-Optimal Measurements and Sublinear Time

1. Problématique et Contexte

Le Compressé Sensing à un bit (1bCS) vise à reconstruire un signal sparse (rares) $x \in \mathbb{R}^n$ à partir d'un nombre réduit de mesures linéaires fortement quantifiées, ne conservant que le signe de chaque mesure : $y = \text{sign}(Ax)$. L'objectif spécifique de cet article est la récupération du support (support recovery), c'est-à-dire l'identification des coordonnées non nulles de $x$ (noté $\text{supp}(x)$), où la sparsité $k = |\text{supp}(x)|$ est bien inférieure à la dimension $n$.

Le défi principal :
Bien que des méthodes existantes permettent de minimiser le nombre de mesures $m$, elles souffrent généralement d'une complexité de décodage de l'ordre de $\Omega(n)$ (linéaire par rapport à la dimension du signal). Cette complexité limite leur applicabilité aux grands systèmes. L'objectif de l'article est de concevoir des schémas de récupération de support avec une complexité de décodage sous-linéaire (idéalement $O(m)$ ou proche), tout en maintenant des bornes de mesures quasi-optimales.

2. Méthodologie et Approche

Les auteurs proposent une nouvelle famille de schémas nommée EDOCS (Efficient Decoding One-bit Compressed Sensing). L'approche repose sur deux piliers conceptuels :

A. Hybridation avec le Group Testing (Test de Groupe)

L'article établit un lien fort entre le 1bCS et le Non-adaptive Group Testing (test de groupe non adaptatif). Dans le test de groupe, on cherche à identifier des éléments défectueux dans un ensemble binaire via des tests logiques (OU/ET).

• Transformation : Les auteurs utilisent des matrices de signature et des techniques de « magnification » ($U$-magnification) pour transformer les mesures 1bCS en un format exploitable par des algorithmes de test de groupe rapides.
• Détection des Singletons : L'idée centrale est d'identifier des « singletons » (mesures correspondant à exactement un élément du support) qui peuvent être décodés en temps quasi-constant.

B. Architecture en Deux Étapes

Pour éviter de parcourir toutes les $n$ colonnes de la matrice de mesure, l'algorithme procède en deux phases :

1. Phase de Candidature (Blocage) : Utilisation d'une matrice combinatoire (basée sur des familles d'union sans liste ou list union-free families) pour identifier un ensemble candidat $S$ contenant la majorité du vrai support. Cette étape utilise la structure de la matrice pour isoler des indices.
2. Phase de Filtrage : Affinement de l'ensemble $S$ en éliminant les faux positifs en comparant les colonnes correspondantes avec les mesures de validation.

3. Contributions Clés et Résultats

Les auteurs présentent trois schémas principaux couvrant différents compromis entre garanties de récupération, nombre de mesures et complexité temporelle.

A. Récupération Universelle Approximative ($\epsilon$-approximate)

• Objectif : Retrouver un support $S$ tel que l'erreur (faux positifs et faux négatifs) soit inférieure à $\epsilon k$.
• Mesures ($m$) : $O(k \epsilon^{-1} \log(n/k) \log n)$.
• Complexité de décodage ($D$) : $O(\epsilon^{-1} m)$.
• Avantage : Complexité sous-linéaire par rapport à $n$.

B. Récupération Universelle Exacte

• Objectif : Retrouver exactement $\text{supp}(x)$ pour tout signal $k$-sparse.
• Mesures ($m$) : $O(k^2 \log(n/k) \log n)$.
• Complexité de décodage ($D$) : $O(km)$.
• Avantage : C'est la première méthode universelle de récupération de support en 1bCS à atteindre une complexité sous-linéaire.

C. Récupération Exacte Probabiliste (EDOCS-EE)

• Objectif : Récupération exacte avec une probabilité d'erreur négligeable pour un signal fixe.
• Technique : Utilisation d'un algorithme de binaire splitting rapide (fast binary splitting) issu du test de groupe, adapté au 1bCS via des matrices « totalement inversibles » (AsTIM) pour éviter les « zéros accidentels » (cas où une combinaison linéaire de signaux s'annule alors que le support est non vide).
• Mesures ($m$) : $O\left(k \frac{\log k}{\log \log k} \log n\right)$.
• Complexité de décodage ($D$) : $O(m)$.
• Avantage : Amélioration significative par rapport à l'état de l'art précédent [YZG25] en réduisant le nombre de mesures et en accélérant le décodage.

4. Signification et Impact

• Briser le goulot d'étranglement linéaire : Cet article démontre qu'il est possible de dépasser la barrière de complexité $\Omega(n)$ dans le contexte du 1bCS, rendant la récupération de support viable pour des dimensions $n$ très élevées (Big Data).
• Nouveau compromis (Trade-off) : Les auteurs montrent qu'il est possible d'obtenir une efficacité computationnelle sous-linéaire au prix d'un facteur logarithmique supplémentaire ($\log n$) dans le nombre de mesures par rapport aux bornes théoriques minimales absolues.
• Innovation Algorithmique : L'adaptation des techniques de test de groupe (comme le fast binary splitting et les matrices d'union sans liste) au cadre du 1bCS, en gérant spécifiquement les problèmes de signe et de zéros accidentels, constitue une contribution méthodologique majeure.
• Comparaison avec l'état de l'art :
  • Pour la récupération approximative, la complexité passe de $O(n \epsilon^{-1} \log(n/k))$ à $O(k \epsilon^{-2} \log n \log(n/k))$.
  • Pour la récupération exacte, elle passe de $O(nk \log n)$ à $O(k^3 \log n \log(n/k))$.

Conclusion

L'article propose des schémas EDOCS qui établissent un nouvel état de l'art pour la récupération de support en 1bCS. En combinant la théorie des ensembles combinatoires, le test de groupe et l'algèbre linéaire, les auteurs réussissent à concevoir des algorithmes dont le temps d'exécution est sous-linéaire par rapport à la dimension du signal, tout en conservant un nombre de mesures proche de l'optimal. Cela ouvre la voie à des applications pratiques dans des domaines où le stockage et le traitement de signaux haute dimension sont critiques.