Abundancia de la muestra

La abundancia de muestras es un paradigma de procesamiento de señales en el que se aprovechan grandes cantidades de mediciones de baja precisión —a menudo muestras de un bit producidas por comparadores con umbrales variables en el tiempo— para recuperar señales o parámetros con alta fidelidad y menor coste computacional. ^{[ 1 ]} En lugar de imponer restricciones difíciles (por ejemplo, semidefinición positiva o rango bajo) durante la reconstrucción, muchos problemas bajo abundancia de muestras se reformulan como tareas de factibilidad lineal sobredeterminadas definidas por desigualdades de semiespacio. Con suficientes mediciones binarias, estas desigualdades confinan la solución a una pequeña región poliédrica alrededor de la verdad fundamental, lo que hace innecesarias las restricciones que antes eran esenciales. Más allá de un número crítico de muestras, la carga algorítmica colapsa repentinamente, un fenómeno que puede denominarse singularidad de abundancia de muestras . ^{[ 2 ]}

Los convertidores analógico-digitales (ADC) de uno o pocos bits son atractivos en aplicaciones como MIMO masivo y radar porque los comparadores son económicos, rápidos y de bajo consumo energético. La introducción de dither o umbrales variables en el tiempo permite que los signos binarios conserven suficiente información estadística para la estimación, incluyendo la covarianza y la recuperación del espectro mediante resultados de la ley del arcoseno generalizada. ^{[ 3 ] [ 4 ]} Las arquitecturas híbridas como Unlimited One-Bit Sampling (UNO) combinan el plegado modular con umbrales de un bit para aumentar aún más el rango dinámico manteniendo un bajo coste de hardware. ^{[ 5 ]} Los esfuerzos relacionados abarcan la estimación de canales MIMO de baja resolución y el procesamiento de radar con datos binarios. ^{[ 6 ] [ 7 ]}

Supongamos que se obtiene una muestra de un bit comparando una medición.${\displaystyle y_{k}}$con un umbral${\displaystyle \tau _{k}}$: ${\displaystyle r_{k}=\operatorname {sgn} (y_{k}-\tau _{k})\in \{-1,+1\}.}$Cada observación produce la desigualdad lineal.${\displaystyle r_{k}(y_{k}-\tau _{k})\geq 0}$. Apilando muchas muestras y escribiendo${\displaystyle \mathbf {y} =\mathbf {A} \mathbf {x} }$para detección lineal da como resultado el poliedro de un bit :

${\displaystyle {\mathcal {P}}_{\mathbf {x} }=\{\ \mathbf {x} \in \mathbb {R} ^{d}\mid \mathbf {P} \mathbf {x} \succeq \mathbf {b} \ \}}$,

dónde${\displaystyle \mathbf {P} }$colecciona filas firmadas de${\displaystyle \mathbf {A} }$y${\displaystyle \mathbf {b} }$apila los términos umbral. Bajo abundancia de muestra (muchas más desigualdades que incógnitas),${\displaystyle {\mathcal {P}}_{\mathbf {x} }}$Por lo general, tiene un volumen finito cerca de la verdad fundamental y se reduce a medida que se agregan más muestras. ^{[ 1 ]}

La singularidad de abundancia de muestras se refiere al cambio de régimen observado en el que, después de superarse un umbral de medición dependiente del problema, los requisitos computacionales se reducen de programas no convexos o restringidos (por ejemplo, formulaciones semidefinidas o con restricción de rango) a proyecciones simples sobre semiplanos lineales. En este régimen, imponer la semidefinición positiva, el rango o la escasez puede resultar innecesario porque el conjunto factible poliédrico ya localiza la solución dentro de la precisión deseada. ^{[ 8 ] [ 1 ]}

Debido a que la abundancia de muestras produce sistemas sobredeterminados de desigualdades lineales, los métodos de proyección son naturales. El algoritmo aleatorio de Kaczmarz (RKA) selecciona una fila al azar y proyecta la iteración; para sistemas consistentes, converge linealmente en esperanza a una tasa gobernada por un número de condición escalado . ^{[ 13 ] [ 14 ]} El método de muestreo de Kaczmarz-Motzkin (SKM) extrae un mini-lote de filas, elige la restricción más violada y proyecta, acelerando a menudo la convergencia en sistemas grandes. ^{[ 15 ]} También se han reportado variantes desplegadas y plug-and-play adaptadas a datos de un bit para mayor velocidad y robustez. ^{[ 1 ]}

La propiedad de volumen finito (FVP) proporciona límites de complejidad de muestra que aseguran que el poliedro formado por desigualdades de un bit tenga un volumen pequeño (por ejemplo, se encuentra dentro de un${\displaystyle \varepsilon }$-bola alrededor de la verdad). Para mediciones isotrópicas, un conjunto de resultados implica que

${\displaystyle m=O(\varepsilon ^{-3})}$Las muestras arrojan error${\displaystyle O(m^{-1/3})}$,

con mejoras${\displaystyle O(\varepsilon ^{-2})}$escalado cuando la señal pertenece a conjuntos estructurados (por ejemplo, vectores dispersos o matrices de bajo rango) cuyas entropías de Kolmogorov son menores. ^{[ 1 ] [ 16 ]} Estas garantías ayudan a explicar por qué las restricciones explícitas de PSD, rango o dispersión pueden volverse redundantes una vez que el número de comparaciones binarias supera un umbral dependiente del problema. ^{[ 1 ]}

• Receptores de baja resolución en comunicaciones y detección MIMO masivas. ^{[ 17 ]}

• Detección por radar y automoción, incluyendo la dirección de llegada basada en covarianza y la compleción de matrices de Hankel de un bit . ^{[ 18 ] [ 19 ]}

• Muestreo ilimitado/de un bit para señales de ancho de banda limitado y tasa de innovación finita, e imágenes HDR con umbrales variables. ^{[ 20 ]}

• Método de Kaczmarz

• Detección comprimida

• recuperación de fase

• Cuantización (procesamiento de señales)