Amostragem compressiva

A amostragem compressiva (também conhecida como detecção comprimida, detecção compressiva, ou amostragem esparsa) é uma técnica de processamento de sinal para aquisição e reconstrução eficiente de um sinal, encontrando soluções para sistemas lineares subdeterminados. Isso se baseia no princípio de que, por meio da otimização, a dispersão de um sinal pode ser explorada para recuperá-lo a partir de muito menos amostras do que o exigido pelo teorema de amostragem de Nyquist-Shannon. Existem duas condições sob as quais a recuperação é possível. ^[1] A primeira é a matriz esparsa, que exige que o sinal seja esparso em algum domínio. A segunda é a incoerência, que é aplicada através da propriedade isométrica, que é suficiente para sinais esparsos. ^{[2] [3]}

Por volta de 2004, Emmanuel Candès, Justin Romberg, Terence Tao e David Donoho provaram que, dado o conhecimento sobre a dispersão de um sinal, ele pode ser reconstruído com ainda menos amostras do que o teorema da amostragem exige. ^{[4] [5]} Essa ideia forma a base da teoria da amostragem compressiva.

A eficácia do Compressed Sensing reside na diferença geométrica fundamental entre as normas matemáticas utilizadas para a reconstrução. O problema original busca a solução de norma ${\displaystyle L_{0}}$ mínima (contagem de elementos não nulos), que é um problema combinatório NP-difícil. A teoria moderna demonstra que, sob certas condições de incoerência, a relaxação para a norma ${\displaystyle L_{1}}$ (soma dos valores absolutos) recupera a mesma solução de forma eficiente.

Geometricamente, enquanto a norma ${\displaystyle L_{2}}$ (mínimos quadrados) possui contornos circulares ou elípticos que tendem a tocar o hiperplano de restrições em regiões densas, a norma ${\displaystyle L_{1}}$ possui contornos poligonais com vértices proeminentes sobre os eixos coordenados. Quando o hiperplano de medições intercepta esse poliedro, a interseção ocorre com alta probabilidade em um vértice, o que promove a esparsidade ao forçar a maioria dos coeficientes a zero.

Para que um sinal ${\displaystyle K}$-esparso de dimensão ${\displaystyle n}$ seja recuperado com alta fidelidade, o número de medições necessárias (${\displaystyle p}$) segue uma escala logarítmica, e não linear:

${\displaystyle p\approx K\log(n/K)}$

Esta redução drástica é fundamentada no Lema de Johnson-Lindenstrauss, que estabelece que projeções aleatórias de pontos em espaços de alta dimensão preservam as distâncias relativas entre eles. Na prática de Ressonância Magnética, isso garante que, desde que a amostragem seja pseudoaleatória e incoerente com a base de representação, a reconstrução será estável mesmo na presença de ruído térmico (${\displaystyle \eta }$).^[6]

O campo de detecção compressiva está relacionado a vários tópicos em processamento de sinal e matemática computacional, como sistemas lineares subdeterminados, teste de grupo, codificação esparsa, multiplexação, amostragem esparsa e taxa finita de inovação. Seu amplo escopo e generalidade permitiram várias abordagens inovadoras aprimoradas em processamento e compressão de sinais, solução de problemas inversos, projeto de sistemas radiantes, imagens de radar e através da parede e caracterização de antenas. ^[7] Técnicas de imagem com forte afinidade com detecção compressiva incluem abertura codificada e fotografia computacional.

O Compressed Sensing (CS) desafia o paradigma tradicional de aquisição de dados ao demonstrar que a estrutura de um sinal (sua esparsidade) pode ser explorada para reduzir a taxa de amostragem abaixo do limite de Nyquist. Matematicamente, o processo de aquisição é modelado como um sistema linear subdeterminado:

${\displaystyle y=Cx+\eta }$

Onde ${\displaystyle x\in \mathbb {R} ^{n}}$ representa o sinal original, ${\displaystyle y\in \mathbb {R} ^{p}}$ é o vetor de medições adquiridas (com ${\displaystyle p\ll n}$), ${\displaystyle C}$ é a matriz de amostragem e ${\displaystyle \eta }$ o ruído de medição.

A eficácia do Compressed Sensing reside na diferença geométrica fundamental entre as normas matemáticas utilizadas para a reconstrução. Enquanto a norma ${\displaystyle L_{2}}$ (mínimos quadrados) possui contornos elípticos que tendem a tocar o hiperplano de restrições em regiões densas, a norma ${\displaystyle L_{1}}$ possui contornos poligonais com vértices proeminentes sobre os eixos coordenados. Quando o hiperplano intercepta esse poliedro, a solução ocorre com alta probabilidade em um vértice, forçando a maioria dos coeficientes a zero e promovendo a esparsidade.

A garantia de reconstrução exata depende da Propriedade de Isometria Restrita (RIP). O Lema de Johnson-Lindenstrauss estabelece que é possível incorporar vetores de alta dimensão em espaços de baixa dimensão preservando distâncias, desde que a matriz de amostragem seja incoerente (como matrizes Gaussianas). Para um sinal ${\displaystyle K}$-esparso de dimensão ${\displaystyle n}$, o número de medições ${\displaystyle p}$ segue a escala logarítmica ${\displaystyle p\approx K\log(n/K)}$.

Para que a recuperação de ${\displaystyle x}$ a partir de ${\displaystyle y}$ seja estável e exata, dois critérios devem ser satisfeitos:

• Esparsidade: O sinal deve admitir uma representação esparsa em uma base transformadora ${\displaystyle \Psi }$ (como Wavelets ou Fourier), de modo que ${\displaystyle x=\Psi s}$, onde ${\displaystyle s}$ possui poucos coeficientes não nulos.
• Incoerência e RIP: A matriz de medição deve ser incoerente com a base de esparsidade, geralmente obtida por amostragem pseudoaleatória. Isso garante a Propriedade de Isometria Restrita (RIP), que assegura que a transformação preserve as distâncias entre vetores esparsos.

A busca pela solução mais esparsa (norma ${\displaystyle L_{0}}$) é um problema computacionalmente intratável (NP-difícil). O avanço da teoria provou que, sob condições de RIP, a minimização da norma L1 recupera a solução correta de forma eficiente via otimização convexa.

Um dos métodos mais robustos é o LASSO (Least Absolute Shrinkage and Selection Operator), formulado como:

${\displaystyle {\hat {s}}=\arg \min _{s}{\frac {1}{2}}\|C\Psi s-y\|_{2}^{2}+\lambda \|s\|_{1}}$

Esta abordagem busca minimizar o erro de ajuste aos dados enquanto penaliza soluções não esparsas através do parâmetro de regularização ${\displaystyle \lambda }$.

Uma das aplicações mais bem-sucedidas da amostragem compressiva ocorre na medicina diagnóstica, especificamente na aceleração de exames de RM.

Na radiologia pediátrica, o CS permite reduzir o tempo de aquisição em até 6 vezes. Como crianças pequenas têm dificuldade em permanecer imóveis, a redução do tempo de exame minimiza a necessidade de sedação e anestesia, reduzindo riscos de complicações como depressão respiratória e bradicardia. Esta prática fundamenta-se no princípio ALARA (As Low As Reasonably Achievable), buscando a máxima qualidade diagnóstica com a mínima intervenção e risco para o paciente.

A otimização convexa desempenha um papel central na ciência de dados moderna, especialmente em problemas de recuperação de sinais e imagens onde o sistema de equações é subdeterminado (mais incógnitas do que medições). A convexidade garante que qualquer mínimo local encontrado pelo algoritmo seja também o mínimo global, o que é essencial para a confiabilidade diagnóstica em áreas como a medicina.

Para resolver o problema de otimização conhecido como LASSO, utilizam-se algoritmos iterativos que buscam minimizar a função de custo composta por um termo de fidelidade aos dados (norma ${\displaystyle L_{2}}$) e um termo de regularização (norma ${\displaystyle L_{1}}$):

${\displaystyle \min _{x}{\frac {1}{2}}\|Cx-y\|_{2}^{2}+\lambda \|x\|_{1}}$

Métodos como o Algoritmo de limiarização iterativa suave (ISTAs) e sua versão acelerada (FISTA) aplicam repetidamente o operador de soft-thresholding para promover a esparsidade da solução a cada iteração. Na prática clínica, esses métodos permitem a reconstrução de imagens médicas complexas em poucos minutos, garantindo que a solução final seja a mais esparsa possível dentro das restrições físicas impostas pelo equipamento de aquisição.^[8]

• BRUNTON, S. L.; KUTZ, J. N. Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control. Cambridge University Press, 2022.
• LUSTIG, M.; DONOHO, D.; PAULY, J. M. Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine, 2007.
• VASANAWALA, S. S. et al. Improved Pediatric MR Imaging with Compressed Sensing. Radiology, 2010.

1. ↑ CS: Compressed Genotyping, DNA Sudoku – Harnessing high throughput sequencing for multiplexed specimen analysis.
2. ↑ Donoho, David L. (2006). «For most large underdetermined systems of linear equations the minimal 1-norm solution is also the sparsest solution». Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132 
3. ↑ M. Davenport, "The Fundamentals of Compressive Sensing", SigView, April 12, 2013.
4. ↑ Candès, Emmanuel J.; Romberg, Justin K.; Tao, Terence (2006). «Stable signal recovery from incomplete and inaccurate measurements» (PDF). Communications on Pure and Applied Mathematics. 59 (8): 1207–1223. Bibcode:2005math......3066C. arXiv:math/0503066. doi:10.1002/cpa.20124. Consultado em 10 de fevereiro de 2011. Cópia arquivada (PDF) em 11 de março de 2012 
5. ↑ Donoho, D.L. (2006). «Compressed sensing». IEEE Transactions on Information Theory. 52 (4): 1289–1306. doi:10.1109/TIT.2006.871582 
6. ↑ Brunton, S. L.; Kutz, J. N. (2022). Data-Driven Science and Engineering. [S.l.]: Cambridge University Press. ISBN 978-1108422093  !CS1 manut: Nomes múltiplos: lista de autores (link)
7. ↑ Andrea Massa; Paolo Rocca; Giacomo Oliveri (2015). «Compressive Sensing in Electromagnetics – A Review». IEEE Antennas and Propagation Magazine. 57 (1): 224–238. Bibcode:2015IAPM...57..224M. doi:10.1109/MAP.2015.2397092 
8. ↑ Lustig, M.; Donoho, D.; Pauly, J. M. (2007). «Sparse MRI: The application of compressed sensing for rapid MR imaging». Magnetic Resonance in Medicine. 58 (6): 1182-1195  !CS1 manut: Nomes múltiplos: lista de autores (link)