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. CS: Compressed Genotyping, DNA Sudoku – Harnessing high throughput sequencing for multiplexed specimen analysis. 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. M. Davenport, "The Fundamentals of Compressive Sensing", SigView, April 12, 2013.

Resumo 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. Essa ideia forma a base da teoria da amostragem compressiva.

Geometria da Reconstrução e o Papel da Norma L1

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 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 (soma dos valores absolutos) recupera a mesma solução de forma eficiente.

Geometricamente, enquanto a norma (mínimos quadrados) possui contornos circulares ou elípticos que tendem a tocar o hiperplano de restrições em regiões densas, a norma 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.

Garantias Teóricas e Limite de Medições

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

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 ().

Usos 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. Técnicas de imagem com forte afinidade com detecção compressiva incluem abertura codificada e fotografia computacional.

Fundamentação Matemática

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:

Onde representa o sinal original, é o vetor de medições adquiridas (com ), é a matriz de amostragem e o ruído de medição.

Geometria da Reconstrução e o Papel da Norma L1 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 (mínimos quadrados) possui contornos elípticos que tendem a tocar o hiperplano de restrições em regiões densas, a norma 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.

Lema de Johnson-Lindenstrauss e RIP 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 -esparso de dimensão , o número de medições segue a escala logarítmica .

Pilares da Reconstrução Para que a recuperação de a partir de seja estável e exata, dois critérios devem ser satisfeitos: Esparsidade: O sinal deve admitir uma representação esparsa em uma base transformadora (como Wavelets ou Fourier), de modo que , onde 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.

Algoritmos de Reconstrução

A busca pela solução mais esparsa (norma ) é 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.

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

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 .

Aplicação em Imagem por Ressonância Magnética (RM)

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. Aplicação em Ciência de Dados e Recuperação Esparsa

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.

Algoritmos Iterativos e Limiarização 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 ) e um termo de regularização (norma ):

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.

Bibliografia Adicional 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.

Referências

Categoria:Otimização Categoria:Álgebra linear Categoria:Teoria da informação