Exceso de exhaustividad

La sobrecompletitud es un concepto del álgebra lineal ampliamente utilizado en matemáticas, informática, ingeniería y estadística (generalmente en forma de marcos sobrecompletos ). Fue introducido por RJ Duffin y AC Schaeffer en 1952. ^{[ 1 ]}

Formalmente, un subconjunto de los vectores${\displaystyle \{\phi _{i}\}_{i\in J}}$de un espacio Banach${\displaystyle X}$, a veces llamado "sistema", está completo si cada elemento en${\displaystyle X}$puede aproximarse arbitrariamente bien en norma mediante combinaciones lineales finitas de elementos en${\displaystyle \{\phi _{i}\}_{i\in J}}$. ^{[ 2 ]} Un sistema se denomina sobrecompleto si contiene más vectores de los necesarios para ser completo, es decir, existen${\displaystyle \phi _{j}\in \{\phi _{i}\}_{i\in J}}$que se puede eliminar del sistema de tal manera que${\displaystyle \{\phi _{i}\}_{i\in J}\setminus \{\phi _{j}\}}$permanece completa. En áreas de investigación como el procesamiento de señales y la aproximación de funciones , la sobrecompletitud puede ayudar a los investigadores a lograr una descomposición más estable, más robusta o más compacta que utilizando una base . ^{[ 3 ]}

La teoría de marcos tiene su origen en un artículo de Duffin y Schaeffer sobre series de Fourier no armónicas . ^{[ 1 ]} Un marco se define como un conjunto de vectores no nulos.${\displaystyle \{\phi _{i}\}_{i\in J}}$de tal manera que para un arbitrario${\displaystyle f\in {\mathcal {H}}}$,

${\displaystyle A\|f\|^{2}\leq \sum _{i\in J}|\langle f,\phi _{i}\rangle |^{2}\leq B\|f\|^{2}}$

dónde${\displaystyle \langle \cdot ,\cdot \rangle }$denota el producto interno,${\displaystyle A}$y${\displaystyle B}$son constantes positivas llamadas límites del marco. Cuando${\displaystyle A}$y${\displaystyle B}$se puede elegir de tal manera que${\displaystyle A=B}$, el marco se denomina marco ajustado. ^{[ 4 ]}

Se puede observar que${\displaystyle {\mathcal {H}}=\operatorname {span} \{\phi _{i}\}}$. Un ejemplo de marco se puede dar de la siguiente manera. Sea cada uno de${\displaystyle \{\alpha _{i}\}_{i=1}^{\infty }}$y${\displaystyle \{\beta _ {i}\}_{i=1}^{\infty }}$ser una base ortonormal de${\displaystyle {\mathcal {H}}}$, entonces

${\displaystyle \{\phi _{i}\}_{i=1}^{\infty }=\{\alpha _{i}\}_{i=1}^{\infty }\cup \{\beta _{i}\}_{i=1}^{\infty }}$

es un marco de${\displaystyle {\mathcal {H}}}$con límites${\displaystyle A=B=2}$.

Dejar${\displaystyle S}$ser el operador de marco,

${\displaystyle Sf=\sum _{i\in J}\langle f,\phi _{i}\rangle \phi _{i}}$

Se dice que un marco que no es una base de Riesz , en cuyo caso consiste en un conjunto de funciones más que una base, es sobrecompleto o redundante . ^{[ 5 ]} En este caso, dado${\displaystyle f\in {\mathcal {H}}}$Puede tener diferentes descomposiciones según el marco. El marco dado en el ejemplo anterior es un marco sobrecompleto.

Cuando se utilizan marcos para la estimación de funciones, puede ser conveniente comparar el rendimiento de diferentes marcos. La parsimonia de las funciones aproximadas mediante diferentes marcos puede considerarse una forma de comparar su rendimiento. ^{[ 6 ]}

Dado un margen de tolerancia${\displaystyle \epsilon }$y un marco${\displaystyle F=\{\phi _{i}\}_{i\in J}}$en${\displaystyle L^{2}(\mathbb {R} )}$, para cualquier función${\displaystyle f\in L^{2}(\mathbb {R} )}$, definimos el conjunto de todas las funciones de aproximación que satisfacen${\displaystyle \|f-{\sombrero {f}}\|<\epsilon }$

${\displaystyle N(f,\epsilon )=\{{\hat {f}}:{\hat {f}}=\sum _{i=1}^{k}\beta _{i}\phi _{i},\|f-{\hat {f}}\|<\epsilon \}}$

Entonces deja

${\displaystyle k_{F}(f,\epsilon )=\inf\{k:{\hat {f}}\in N(f,\epsilon )\}}$

${\displaystyle k(f,\epsilon)}$indica la parsimonia de utilizar el marco${\displaystyle F}$para aproximar${\displaystyle f}$. Diferente${\displaystyle f}$pueden tener diferentes${\displaystyle k}$basado en la dureza a aproximar con elementos en el marco. El peor caso para estimar una función en${\displaystyle L^{2}(\mathbb {R} )}$se define como

${\displaystyle k_{F}(\epsilon )=\sup _{f\in L^{2}(\mathbb {R} )}\{k_{F}(f,\epsilon )\}}$

Para otro fotograma${\displaystyle G}$, si${\displaystyle k_{F}(\epsilon )<k_{G}(\epsilon )}$, luego marco${\displaystyle F}$es mejor que el marco${\displaystyle G}$en el nivel${\displaystyle \epsilon }$. Y si existe un${\displaystyle \gamma }$que para cada${\displaystyle \epsilon <\gamma}$, tenemos${\displaystyle k_{F}(\epsilon )<k_{G}(\epsilon )}$, entonces${\displaystyle F}$es mejor que${\displaystyle G}$en general.

Los marcos sobrecompletos generalmente se construyen de tres maneras.

1. Combine un conjunto de bases, como la base de ondículas y la base de Fourier, para obtener un marco sobrecompleto.
2. Amplíe el rango de parámetros en algún marco, como en el marco de Gabor y el marco de ondículas , para obtener un marco sobrecompleto.
3. Agregue algunas funciones adicionales a una base completa existente para lograr un marco sobrecompleto.

A continuación se muestra un ejemplo de marco sobrecompleto. Los datos recopilados se encuentran en un espacio bidimensional, y en este caso, una base con dos elementos debería ser suficiente para explicarlos todos. Sin embargo, cuando se incluye ruido en los datos, una base podría no ser capaz de expresar sus propiedades. Si se utiliza un marco sobrecompleto con cuatro elementos, correspondientes a los cuatro ejes de la figura, para representar los datos, cada punto podría tener una buena representación mediante dicho marco.

• 
  Un ejemplo de un marco sobrecompleto

La flexibilidad del marco sobrecompleto es una de sus principales ventajas cuando se utiliza para expresar una señal o aproximar una función. Sin embargo, debido a esta redundancia, una función puede tener múltiples expresiones bajo un marco sobrecompleto. ^{[ 7 ]} Cuando el marco es finito, la descomposición se puede expresar como

${\displaystyle f=Ax}$

dónde${\displaystyle f}$es la función que se desea aproximar,${\displaystyle A}$es la matriz que contiene todos los elementos del marco, y${\displaystyle x}$son los coeficientes de${\displaystyle f}$bajo la representación de${\displaystyle A}$. Sin ninguna otra restricción, el marco elegirá dar${\displaystyle x}$con norma mínima en${\displaystyle L^{2}(\mathbb {R} )}$. Basándose en esto, también se pueden considerar otras propiedades al resolver la ecuación, como la escasez. Por lo tanto, diferentes investigadores han estado trabajando en la resolución de esta ecuación agregando otras restricciones en la función objetivo. Por ejemplo, una restricción que minimiza${\displaystyle x}$norma de en${\displaystyle L^{1}(\mathbb {R} )}$puede utilizarse para resolver esta ecuación. Esto debería ser equivalente a la regresión Lasso en la comunidad estadística. El enfoque bayesiano también se utiliza para eliminar la redundancia en un marco sobrecompleto. Lweicki y Sejnowski propusieron un algoritmo para el marco sobrecompleto al considerarlo como un modelo probabilístico de los datos observados. ^{[ 7 ]} Recientemente, el marco de Gabor sobrecompleto se ha combinado con el método de selección de variables bayesianas para lograr coeficientes de expansión de norma pequeños en${\displaystyle L^{2}(\mathbb {R} )}$y escasez en los elementos. ^{[ 8 ]}

En el análisis moderno del procesamiento de señales y otros campos de la ingeniería, se proponen y utilizan diversos marcos sobrecompletos. Aquí se presentan y analizan dos marcos de uso común: los marcos de Gabor y los marcos de ondículas.

Los marcos de Gabor sobrecompletos y los marcos de ondículas se han utilizado en diversas áreas de investigación, incluyendo detección de señales, representación de imágenes, reconocimiento de objetos, reducción de ruido , teoría del muestreo, teoría de operadores , análisis armónico , aproximación dispersa no lineal , operadores pseudodiferenciales , comunicaciones inalámbricas, geofísica, computación cuántica y bancos de filtros . ^{[ 3 ] [ 5 ]}