Propriedade de isometria restrita (RIP) na detecção compressiva

A propriedade isometry restrita declara que: para qualquer vetor separado . A constante de isometria restrita é , .

(1 - δ_{S}) | | x | |_{2}^{2} \leq | | A x | |_{2}^{2} \leq (1 + δ_{S}) | | x | |_{2}^{2}

$\begin{equation} (1-\delta_S)||x||_2^2 \le ||A x||_2^2 \le (1+\delta_S)||x||_2^2 \end{equation}$

S

$S$

x

$x$

δ_{S}

$\delta_S$

0 < δ_{S} < 1

$0 < \delta_S < 1$

Isso significa que é garantido que a matriz altere apenas o comprimento de qualquer vetor "muito pouco", desde que o vetor seja pelo menos separado em (tem no máximo coeficientes diferentes de zero). $A$ $x$ $x$ $S$ $S$

Suponha que tenhamos vetores arbitrários separados . Para poder reconstruir tais vetores em geral, a partir de medidas tomadas como , precisamos ter certeza de que é possível distinguir entre as medidas e de quaisquer dois vetores. Se para quaisquer dois vetores e , não poderíamos distingui-los e reconstruí-los sem ambiguidade. Portanto, precisamos garantir que as medidas de quaisquer dois vetores separados por sejam "suficientemente diferentes". $\frac{S}{2}$ $x$ $y = A x$ $y_1 = A x_1$ $y_2 = A x_2$ $y_1 = y_2$ $x_1$ $x_2$ $\frac{S}{2}$

Se calcularmos a diferença entre quaisquer dois vetores separados por , sua diferença poderá ser no máximo separada. Portanto, para reconstruir qualquer vetor separado corretamente das medições feitas com , a propriedade isometry restrita quantifica quão bem nos permite fazer isso (quanto menor , melhor). $\frac{S}{2}$ $S$ $\frac{S}{2}$ $A$ $A$ $\delta_S$

Para uma introdução precoce ao sensor comprimido e à propriedade de isometria restrita (e outros conceitos), consulte Candès & Wakin, 2008 .

Thomas Arildsen
fonte

Notemos também que a constante não precisa ser a mesma nos dois lados, por exemplo, matriz sensora gaussiana. Por favor, veja o artigo recente. arxiv.org/abs/1410.1956

δ_{S}

$\delta_{S}$

Oliver

A propriedade fornecida deve valer para qualquer sub-matriz de ?

A

$A$

Dilawar

pode-se verificar na propriedade RIP uma matriz concreta na prática com um algoritmo?

Charlie Parker

@CharlieParker não, infelizmente não. Ele envolve o cálculo do SVD de todas as possíveis -column sub-matrizes de . Isto torna-se rapidamente um número irrealista de combinações para calcular mesmo para de tamanho modesto . E lembre-se de que a detecção compressiva funciona melhor quanto maior o tamanho de e .

S

$S$

A

$A$

A

$A$

A

$A$

x

$x$

Thomas Arildsen 31/03/19

Propriedade de isometria restrita (RIP) na detecção compressiva

Respostas: