Confusão sobre o problema de detecção compactada

Eu li algumas referências, incluindo isso .

Estou meio confuso com o problema de otimização que o sensor compactado cria e tenta resolver. É isso

ou e

ou / e algo mais?

Brian está no local. Mas acho útil adicionar algum contexto de detecção compactado.

Primeiro, observe que a chamada norma 0 - a função de cardinalidade ou o número de valores diferentes de zero em - não é uma norma . Provavelmente, é melhor escrevê-lo como algo como em qualquer coisa, menos nos contextos mais casuais. Não me interpretem mal, você está em boa companhia quando usa a abreviação , mas acho que tende a gerar confusão. x cartão ( x ) ″ x ″ $\|x\|_0$$x$$\mathop{\textbf{card}}(x)$$\|x\|_0$

As pessoas sabem há muito tempo que minimizar a norma tende a produzir soluções esparsas. Existem algumas razões teóricas para isso que têm a ver com complementaridade linear. Mas o mais interessante não foi que as soluções eram escassas, mas que eram frequentemente as mais escassas possíveis . Ou seja, minimizar realmente fornece a solução de cardinalidade mínima em certos casos úteis. (Como eles descobriram isso, quando o problema mínimo de cardinalidade é NP-difícil? Ao construir problemas artificiais com soluções esparsas conhecidas.) Isso não era algo que a teoria da complementaridade linear pudesse prever. ″ x ″ 1 ″ x ″ $\ell_1$$\|x\|_1$$\|x\|_1$

O campo do sensor comprimido nasceu quando os pesquisadores começaram a identificar condições na matriz que lhes permitiam garantir antecipadamente que a solução também era a mais escassa. Veja, por exemplo, os primeiros artigos de Candés, Romberg e Tao e outras discussões sobre a propriedade Restricted isometry, ou RIP . Outro site útil, se você realmente quiser se aprofundar em alguma teoria, é a página de sensores comprimidos de Terence Tao .ℓ $A$$\ell_1$

Gostaríamos muito de poder resolver

$\min \| x \|_{0}$

st

$Ax=b$

mas este problema é um problema de otimização combinatória NP-rígido que é impraticável para resolver na prática, quando , , e são de tamanhos típicos na detecção de compressão. É possível resolver com eficiênciax $A$$x$$b$

$\min \| x \|_{1}$

st

$Ax=b$

tanto na teoria (isso pode ser feito em tempo polinomial) quanto na prática computacional, mesmo para problemas razoavelmente grandes que surgem no sensor de compressão. Nós usamos como um "substituto" para o . Isso tem alguma justificativa intuitiva (a minimização de uma norma prefere soluções com menos entradas diferentes de zero em ), bem como justificativas teóricas muito mais sofisticadas (teoremas da forma "Se tem uma solução k-esparsa, minimizando encontrará essa solução com alta probabilidade. " ″ x ″ 0 x A x = b ″ x ″ $\| x \|_{1}$$\| x \|_{0}$$x$$Ax=b$$\| x \|_{1}$

Na prática, como os dados geralmente são barulhentos, a restrição exata geralmente é substituída por uma restrição do formato . $Ax=b$$\| Ax - b \|_{2} \leq \delta$

Também é bastante comum trabalhar com uma forma variacional do problema restrito, onde, por exemplo, podemos minimizar .$\min \| Ax - b\|_{2}^{2} + \lambda \| x \|_{1}$

Não tenho nada a acrescentar à explicação de Brians e Michaels sobre vs. ℓ 0 . Mas como a pergunta parece ser sobre a detecção compactada, gostaria de acrescentar meu ponto de vista: a detecção compactada não é sobre resolver min ″ x ″ $\ell^1$$\ell^0$ nemcerca de min ″ x ″

É possível identificar sinais esparsos a partir de algumas medições.

O Sensor de compressão é realmente sobre o menor número possível de medições para identificar um sinal em uma determinada classe de sinais.

Uma frase cativante é:

Por que sua câmera de 5 megapixels realmente mede 15 milhões de valores (três para cada pixel) que custam 15 megabytes de dados quando ela armazena apenas cerca de 2 megabytes (após a compactação)?
Seria possível medir os 2 megabytes imediatamente?

Existem estruturas bastante diferentes possíveis:

• medições lineares
• não lineares (por exemplo, "sem fases")
• dados vetoriais, dados matriciais / tensores
• escarsidade como apenas o número de não-zeros
• esparsidade como "baixa patente" ou mesmo "baixa complexidade").

E também existem mais métodos para calcular soluções esparsas, como busca de correspondência (variantes como busca de correspondência ortogonal (OMP), busca de correspondência ortogonal regularizada (ROMP), CoSaMP) ou os métodos mais recentes baseados em algoritmos de transmissão de mensagens .

$\ell^1$$\ell^0$

Se alguém, no entanto, está interessado apenas em obter soluções esparsas para sistemas lineares, faz algo que eu chamaria de reconstrução esparsa .