Sobre reconstrução esparsa a partir de medições de Fourier e Gaussianas

Resumo Este artigo melhora as garantias melhor conhecidas para a reconstrução exata de um sinal esparso f a partir de uma pequena amostra universal de medições de Fourier. O método para reconstrução que recentemente ganhou destaque na teoria de aproximação esparsa é relaxar este problema altamente não convexo para um problema convexo e então resolvê-lo como um programa linear. Mostramos que existe um conjunto de frequências Ω tal que é possível reconstruir exatamente todo sinal f esparso de comprimento n a partir de suas frequências em Ω, usando a relaxação convexa, e Ω tem tamanho A. Um conjunto aleatório Ω satisfaz isso com alta probabilidade. Esta estimativa é ótima dentro dos fatores log log n e log 3 r. Também fornecemos um argumento relativamente curto para um problema semelhante com k (r, n) ≈ r 12 + 8 log(n / r) medições gaussianas. Usamos métodos de análise funcional geométrica e teoria da probabilidade em espaços de Banach, o que torna nossos argumentos bastante curtos. © 2007 Wiley Periodicals, Inc.