Recuperación dispersa y compresión

Entonces x y x+h producen la misma y. Sin una restricción adicional no se recupera cualquier vector de forma única.

Llamamos s-dispersa a una señal con como máximo s coordenadas no nulas. La restricción se refiere a una representación concreta: una señal puede ser dispersa en una base y no en otra. Si x=Bc y c es disperso, la matriz que mide sus coeficientes es AB.

La notación cuenta coordenadas no nulas. No es una norma: multiplicar un vector por dos no duplica ese conteo. La norma sí suma amplitudes absolutas y es convexa.

Una señal aproximadamente dispersa tiene una cola pequeña. es el error de la mejor aproximación s-dispersa en ℓ¹: se conservan s coordenadas de mayor módulo y se suma el módulo de las restantes.

Dos señales s-dispersas difieren en como máximo 2s posiciones. Por eso no debe existir un h≠0 del núcleo con a lo sumo 2s no nulos. Esta condición garantiza unicidad para todas las señales de esa clase.

También es necesaria: se divide el soporte de tal h en S y T con a lo sumo s posiciones cada una. Las señales y − son distintas, s-dispersas y tienen la misma medición. Se escribe spark(A)>2s, donde spark es el soporte mínimo de un vector no nulo del núcleo.

Basis pursuit sustituye el objetivo por ℓ¹. En el caso real se formula como programa lineal: minimizar la suma de con −≤≤ y Az=y. Es un problema convexo.

Convexo significa que optimizamos eficazmente el objetivo elegido bajo condiciones habituales del algoritmo. No demuestra que ese objetivo seleccione la señal verdadera. Puede haber empates o preferir una señal diferente. Hay que estudiar A, no solo el método de cálculo.

NSP de orden s exige, para todo h≠0 en ker A y todo S con |S|≤s, . La parte invisible de la medición no puede concentrar la mitad o más de su amplitud en un soporte admisible.

Si x está soportada en S y z=x+h es otra señal factible, .

Así x es el mínimo único. Si NSP falla, x=− y z=ᶜ miden igual y z no cuesta más: tampoco hay recuperación uniforme única.

RIP de orden k exige para todo z k-disperso. Una condición clásica suficiente para recuperación estable por ℓ¹ es δ₂ₛ<√2−1. No es necesaria ni la mejor constante de todas las variantes.

La coherencia compara productos de columnas normalizadas: columnas idénticas no distinguen qué coordenada actuó. Ciertas familias aleatorias dan garantías con alta probabilidad y tamaños de orden s·log(N/s), con condiciones y constantes propias. No toda matriz de esas dimensiones tiene la garantía.

Si y=Ax+e y ‖e‖₂≤ε, sustituimos la igualdad por una tolerancia: minimizar ‖z‖₁ sujeto a ‖Az−y‖₂≤ε. Bajo la condición RIP suficiente indicada, . Las constantes dependen del operador y de su garantía.

La cola mide falta de dispersión exacta; ε mide ruido de medición. La tolerancia debe contener el error real y usar las mismas unidades. Una respuesta con residual pequeño no asegura poco error de señal si la matriz pierde información.

LASSO en esta forma minimiza , con λ>0. Un paso proximal toma v=z−αAᵀ(Az−y) y aplica a cada coordenada.

Un tamaño 0<α≤1/‖A‖₂² es una elección estándar para el descenso proximal cuando A≠0. El algoritmo reduce amplitudes y puede anular pequeñas coordenadas. Su convergencia optimiza la penalización; no demuestra NSP ni convierte el sesgo del umbral en mediciones exactas.