Partially deterministic sampling for compressed sensing with denoising guarantees

Resumo Técnico: Amostragem Parcialmente Determinística para Compressed Sensing com Garantias de Remoção de Ruído

1. O Problema

O Compressed Sensing (CS) permite a recuperação de sinais de alta dimensão a partir de poucas medições, assumindo que o sinal possui uma estrutura de baixa dimensão (como esparsidade ou pertencimento a um modelo generativo). Tradicionalmente, quando as medições são escolhidas a partir das linhas de uma matriz unitária (ex: Transformada de Fourier em MRI), a teoria assume que essas linhas são selecionadas aleatoriamente (amostragem com ou sem reposição).

No entanto, na prática (especialmente em imagens médicas como MRI), certas medições (ex: componentes de baixa frequência) são cruciais e devem ser capturadas com certeza. A amostragem puramente aleatória (com reposição) falha em garantir a inclusão dessas linhas críticas e pode gerar redundância (amostrar a mesma linha várias vezes). A amostragem sem reposição evita redundância, mas ainda não garante a inclusão determinística de medições de alta coerência.

O desafio central abordado neste trabalho é desenvolver um esquema de amostragem que:

1. Garanta a inclusão determinística de medições críticas (probabilidade = 1).
2. Mantenha a aleatorização para as demais medições para preservar propriedades teóricas de recuperação.
3. Forneça garantias teóricas rigorosas de recuperação e remoção de ruído (denoising) sob ruído gaussiano.

2. Metodologia

Os autores propõem e analisam um esquema de Amostragem Bernoulli Otimizada.

• Modelo de Amostragem: Em vez de escolher um número fixo de linhas, cada linha da matriz unitária $F$ é incluída na matriz de amostragem $S$ independentemente com uma probabilidade $w_i \in [0, 1]$.
  • Se $w_i = 1$, a medição é determinística (sempre incluída).
  • Se $w_i < 1$, a medição é aleatória.
• Coerência Local: O método utiliza o vetor de coerência local $\alpha$, que quantifica o alinhamento de cada vetor de medição com o conjunto de sinais a priori (o cone $T$).
• Pesos Otimizados ($w^\circ$): Os autores derivam uma expressão de forma fechada para os pesos de probabilidade ótimos. A estratégia é:
  1. Ordenar as coerências locais $\alpha$ em ordem crescente.
  2. Identificar um conjunto de medições com alta coerência para serem amostradas deterministicamente ($w_i = 1$).
  3. Atribuir probabilidades menores às medições restantes, de forma que o número esperado de medições seja $m$.
• Pré-condicionamento: Utiliza-se uma matriz de pré-condicionamento diagonal $D$ para equilibrar o efeito das probabilidades de amostragem não uniformes, garantindo que a matriz resultante satisfaça a Propriedade de Isometria Restrita (RIP).

3. Contribuições Principais

1. Garantias de Remoção de Ruído (Denoising):

   • Estabelecem as primeiras limites teóricos de erro de recuperação e remoção de ruído para esquemas de amostragem Bernoulli com pesos de probabilidade variáveis e ruído gaussiano.
   • Estendem a teoria existente (que focava em amostragem com reposição) para este cenário híbrido.

2. Fórmula de Pesos em Forma Fechada:

   • Fornecem uma expressão explícita para os pesos ótimos $w^\circ$, evitando a necessidade de resolver equações auxiliares complexas ou problemas de otimização numérica para encontrar constantes de normalização, como exigido em trabalhos anteriores.

3. Melhoria nos Limites de Complexidade de Amostragem:

   • Derivam um novo limite de complexidade de amostragem que depende de uma nova quantidade $L(\alpha, m)$, que é estritamente menor ou igual ao limite anterior baseado na norma $\ell_2$ das coerências ($\|\alpha\|_2$).
   • A melhoria surge porque o novo limite ignora as coerências locais das medições que foram "saturadas" (amostradas deterministicamente), reduzindo o custo teórico necessário para a recuperação.

4. Teoria Geral para Seletores Bernoulli:

   • Desenvolvem uma teoria de recuperação e denoising válida para qualquer esquema de seleção Bernoulli, onde o esquema otimizado é identificado como o minimizador de um limite de complexidade associado.

4. Resultados e Evidências

• Resultados Teóricos:

  • O Teorema 2.8 fornece o limite de erro de recuperação para o esquema otimizado. O limite mostra que o erro depende de $L(\alpha, m)$, que diminui à medida que o número de medições $m$ aumenta (devido ao aumento do número de medições saturadas).
  • A Proposição 2.10 prova que $L(\alpha, m) \le \|\alpha\|_2$, demonstrando uma melhoria teórica sobre a amostragem com reposição.
  • O Exemplo de Brinquedo (Seção 6) ilustra que, em cenários onde medições críticas são essenciais, a amostragem sem reposição otimizada pode falhar com probabilidade constante (mesmo para $n \to \infty$), enquanto a amostragem Bernoulli otimizada falha com probabilidade que tende a zero, pois garante a inclusão das medições críticas.

• Resultados Numéricos (Seção 7):

  • Experimentos: Realizados no conjunto de dados CELEBA (imagens faciais) com dois priors: sinais esparsos (base de wavelets Haar) e sinais gerados por modelos generativos (VAE).
  • Comparação: O esquema Bernoulli otimizado superou consistentemente a amostragem com reposição e a amostragem sem reposição (com e sem pré-condicionadores heurísticos).
  • Desempenho:
    • Para sinais esparsos, a amostragem Bernoulli otimizada foi superior, especialmente porque consegue lidar com caudas pesadas de coerência local que confundem a amostragem sem reposição.
    • Para sinais muito esparsos ($k < 200$), a amostragem puramente determinística (selecionar as $k$ maiores coerências) performou melhor, mas o método proposto oferece o melhor compromisso geral.
  • Eficiência Computacional: Diferente de métodos sem reposição que exigem rejeição de amostras repetidas (o que se torna computacionalmente inviável quando as probabilidades de medições restantes são muito baixas), a amostragem Bernoulli é computacionalmente eficiente e fácil de implementar.

5. Significado e Impacto

Este trabalho preenche uma lacuna crítica entre a teoria idealizada de amostragem aleatória e as necessidades práticas de aplicações como a Ressonância Magnética (MRI).

• Praticidade: Permite que engenheiros e pesquisadores incorporem conhecimento de domínio (ex: "as baixas frequências são essenciais") diretamente no esquema de amostragem sem perder as garantias teóricas de recuperação.
• Robustez: Oferece garantias de que medições críticas não serão perdidas por acaso, um risco inerente a esquemas puramente aleatórios.
• Avanço Teórico: Introduz novas ferramentas analíticas para lidar com a mistura de determinismo e aleatoriedade em problemas de otimização estocástica, melhorando os limites de complexidade de amostragem conhecidos na literatura.

Em suma, o artigo propõe um método híbrido que é teoricamente superior em termos de limites de erro e praticamente viável em termos de implementação e desempenho em recuperação de imagens reais.