Sobrecompletitud

Concepto en álgebra lineal

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

Formalmente, un subconjunto de los vectores de un espacio de Banach , a veces llamado "sistema", es completo si cada elemento en puede aproximarse arbitrariamente bien en norma mediante combinaciones lineales finitas de elementos en . ^[2] Un sistema se llama sobrecompleto si contiene más vectores de los necesarios para estar completo, es decir, existen elementos que pueden eliminarse del sistema y que permanecen completos. 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 usar una base . ^[3] ${\displaystyle \{\phi _{i}\}_{i\in J}}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \{\phi _{i}\}_{i\in J}}$ ${\displaystyle \phi _{j}\in \{\phi _{i}\}_{i\in J}}$ ${\displaystyle \{\phi _{i}\}_{i\in J}\setminus \{\phi _{j}\}}$

Relación entre sobrecompletitud y marcos.

La teoría de los marcos se origina 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 distintos de cero tales que para un valor arbitrario , ${\displaystyle \{\phi _{i}\}_{i\in J}}$ ${\displaystyle f\in {\mathcal {H}}}$

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

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

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

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

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

Sea el operador del marco, ${\displaystyle S}$

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

Un marco que no es una base de Riesz , en cuyo caso consta de un conjunto de funciones más que de una base, se dice que es sobrecompleto o redundante . ^[5] En este caso, dado , puede tener diferentes descomposiciones en función del marco. El marco dado en el ejemplo anterior es un marco sobrecompleto. ${\displaystyle f\in {\mathcal {H}}}$

Cuando se utilizan marcos para la estimación de funciones, es posible que desee comparar el rendimiento de diferentes marcos. La parsimonia de las funciones de aproximación por diferentes marcos puede considerarse como una forma de comparar sus desempeños. ^[6]

Dada una tolerancia y un marco en , para cualquier función , defina el conjunto de todas las funciones aproximadas que satisfacen ${\displaystyle \epsilon }$ ${\displaystyle F=\{\phi _{i}\}_{i\in J}}$ ${\displaystyle L^{2}(\mathbb {R} )}$ ${\displaystyle f\in L^{2}(\mathbb {R} )}$ ${\displaystyle \|f-{\hat {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 para aproximar . Diferentes pueden tener diferencias según la dureza que se aproximará a los elementos del marco. El peor caso para estimar una función se define como ${\displaystyle F}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle k}$ ${\displaystyle L^{2}(\mathbb {R} )}$

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

Para otro marco , si , entonces el marco es mejor que el marco nivelado . Y si existe algo que para cada uno tenemos , entonces es mejor que en términos generales. ${\displaystyle G}$ ${\displaystyle k_{F}(\epsilon )<k_{G}(\epsilon )}$ ${\displaystyle F}$ ${\displaystyle G}$ ${\displaystyle \epsilon }$ ${\displaystyle \gamma }$ ${\displaystyle \epsilon <\gamma }$ ${\displaystyle k_{F}(\epsilon )<k_{G}(\epsilon )}$ ${\displaystyle F}$ ${\displaystyle G}$

Los marcos sobrecompletos suelen construirse de tres maneras.

1. Combine un conjunto de bases, como la base wavelet 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 wavelet , para tener un marco sobrecompleto.
3. Agregue algunas otras funciones a una base completa existente para lograr un marco sobrecompleto.

A continuación se muestra un ejemplo de un marco sobrecompleto. Los datos recopilados se encuentran en un espacio bidimensional, y en este caso una base con dos elementos debería poder explicar todos los datos. Sin embargo, cuando se incluye ruido en los datos, es posible que una base no pueda expresar las propiedades de los datos. Si se utiliza un marco sobrecompleto con cuatro elementos correspondientes a los cuatro ejes de la figura para expresar los datos, cada punto podría tener una buena expresión en el marco sobrecompleto.

• 
  Un ejemplo de un marco sobrecompleto.

La flexibilidad del marco sobrecompleto es una de sus ventajas clave 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 en un marco sobrecompleto. ^[7] Cuando el marco es finito, la descomposición se puede expresar como

${\displaystyle f=Ax}$

donde está la función que se quiere aproximar, es la matriz que contiene todos los elementos del marco y son los coeficientes de bajo la representación de . Sin ninguna otra limitación, el marco optará por dar con norma mínima en . En base a esto, también se pueden considerar algunas otras propiedades al resolver la ecuación, como la escasez. Por eso, diferentes investigadores han estado trabajando para resolver esta ecuación agregando otras restricciones en la función objetivo. Por ejemplo, se puede utilizar una restricción que minimice la norma de para resolver esta ecuación. Esto debería ser equivalente a la regresión de 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 viéndolo 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 normativos pequeños y escasez de elementos. ^[8] ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle L^{2}(\mathbb {R} )}$ ${\displaystyle x}$ ${\displaystyle L^{1}(\mathbb {R} )}$ ${\displaystyle L^{2}(\mathbb {R} )}$

Ejemplos de fotogramas sobrecompletos

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

Marcos Gabor

En la transformación de Fourier habitual, la función en el dominio del tiempo se transforma al dominio de la frecuencia. Sin embargo, la transformación sólo muestra la propiedad de frecuencia de esta función y pierde su información en el dominio del tiempo. Si una función de ventana , que solo tiene un valor distinto de cero en un intervalo pequeño, se multiplica por la función original antes de operar la transformación de Fourier, tanto la información en el dominio del tiempo como de la frecuencia pueden permanecer en el intervalo elegido. Cuando se utiliza una secuencia de traducción en la transformación, la información de la función en el dominio del tiempo se mantiene después de la transformación. ${\displaystyle g}$ ${\displaystyle g}$

dejar que los operadores

${\displaystyle T_{a}:L^{2}(R)\rightarrow L^{2}(R),(T_{a}f)(x)=f(x-a)}$

${\displaystyle E_{b}:L^{2}(R)\rightarrow L^{2}(R),(E_{b}f)(x)=e^{2\pi ibx}f(x)}$

${\displaystyle D_{c}:L^{2}(R)\rightarrow L^{2}(R),(D_{c}f)(x)={\frac {1}{\sqrt {c}}}f\left({\frac {x}{c}}\right)}$

Un marco de Gabor (llamado así por Dennis Gabor y también llamado marco de Weyl - Heisenberg ) se define como la forma , donde y es una función fija. ^[5] Sin embargo, no para todos y forma un marco en . Por ejemplo, cuando no es un marco para . Cuando , es posible que sea un marco, en cuyo caso es una base Riesz. Entonces la posible situación para ser un marco sobrecompleto es . La familia Gabor también es un marco y comparte los mismos límites que ${\displaystyle L^{2}(R)}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ ${\displaystyle a,b>0}$ ${\displaystyle g\in L^{2}(R)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ ${\displaystyle L^{2}(R)}$ ${\displaystyle ab>1}$ ${\displaystyle L^{2}(R)}$ ${\displaystyle ab=1}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ ${\displaystyle ab<1}$ ${\displaystyle \{E_{mb/c}T_{nac}g_{c}\}_{m,n\in Z}}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}.}$

En el marco Gabor se pueden utilizar diferentes tipos de funciones de ventana . Aquí se muestran ejemplos de tres funciones de ventana y la condición para que el sistema Gabor correspondiente sea un marco se muestra a continuación. ${\displaystyle g}$

• 
  Tres funciones de ventana utilizadas en la generación de marcos de Gabor.

(1) , es un marco cuando ${\displaystyle g(x)=e^{-x^{2}}}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ ${\displaystyle ab<0.994}$

(2) , es un marco cuando ${\displaystyle g(x)={\frac {1}{cosh(\pi x)}}}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$ ${\displaystyle ab<1}$

(3) , donde está la función indicadora. La situación para ser un marco es la siguiente. ${\displaystyle g(x)=I_{[0,c)}(x)}$ ${\displaystyle I(x)}$ ${\displaystyle \{E_{mb}T_{na}g\}_{m,n\in Z}}$

1) o , no un marco ${\displaystyle a>c}$ ${\displaystyle a>1}$

2) y no un marco ${\displaystyle c>1}$ ${\displaystyle a=1}$

3) , es un marco ${\displaystyle a\leq c\leq 1}$

4) y es un irracional, y , es un marco ${\displaystyle a<1}$ ${\displaystyle c\in (1,2)}$

5) , y son primos relativos, no un marco ${\displaystyle a={\frac {p}{q}}<1}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle 2-{\frac {1}{q}}<c<2}$

6) y , donde y es un número natural, no un marco ${\displaystyle {\frac {3}{4}}<a<1}$ ${\displaystyle c=L-1+L(1-a)}$ ${\displaystyle L\geq 3}$

7) , , , donde es el número entero más grande que no excede , es un marco. ${\displaystyle a<1}$ ${\displaystyle c>1}$ ${\displaystyle |c-[c]-{\frac {1}{2}}|<{\frac {1}{2}}-a}$ ${\displaystyle [c]}$ ${\displaystyle c}$

La discusión anterior es un resumen del capítulo 8 en. ^[5]

Marcos wavelet

Una colección de wavelets generalmente se refiere a un conjunto de funciones basadas en ${\displaystyle \psi }$

${\displaystyle \{2^{\frac {j}{2}}\psi (2^{j}x-k)\}_{j,k\in Z}}$

Esto forma una base ortonormal para . Sin embargo, cuando se pueden tomar valores en , el conjunto representa un marco sobrecompleto y se denomina base wavelet no diezmada. En el caso general, un marco wavelet se define como un marco de la forma ${\displaystyle L^{2}(R)}$ ${\displaystyle j,k}$ ${\displaystyle R}$ ${\displaystyle L^{2}(R)}$

${\displaystyle \{a^{\frac {j}{2}}\psi (a^{j}x-kb)\}_{j,k\in Z}}$

dónde y .​ El límite superior e inferior de este marco se puede calcular de la siguiente manera. Sea la transformada de Fourier para ${\displaystyle a>1}$ ${\displaystyle b>0}$ ${\displaystyle \psi \in L^{2}(R)}$ ${\displaystyle {\hat {\psi }}(\gamma )}$ ${\displaystyle \psi \in L^{1}(R)}$

${\displaystyle {\hat {\psi }}(\gamma )=\int _{R}\psi (x)e^{-2\pi ix\gamma }dx}$

Cuando sean fijos, defina ${\displaystyle a,b}$

${\displaystyle G_{0}(\gamma )=\sum _{j\in Z}|{\hat {\psi }}(a^{j}\gamma )|^{2}}$

${\displaystyle G_{1}(\gamma )=\sum _{k\neq 0}\sum _{j\in Z}|{\hat {\psi }}(a^{j}\gamma ){\hat {\psi }}(a^{j}\gamma +{\frac {k}{b}})|}$

Entonces

${\displaystyle B={\frac {1}{b}}\sup _{|\gamma |\in [1,a]}(G_{0}(\gamma )+G_{1}(\gamma ))<\infty }$

${\displaystyle A={\frac {1}{b}}\inf _{|\gamma |\in [1,a]}(G_{0}(\gamma )-G_{1}(\gamma ))>0}$

Además, cuando

${\displaystyle \sum _{j\in Z}|{\hat {\psi }}(2^{j}\gamma )|^{2}=A}$

${\displaystyle \sum _{j=0}^{\infty }{\hat {\psi }}(2^{j}\gamma ){\overline {{\hat {\psi }}(2^{j}(\gamma +q))}}=0}$, para todos los enteros impares ${\displaystyle q}$

el marco generado es un marco ajustado. ${\displaystyle \{\psi _{j,k}\}_{j,k\in Z}}$

La discusión en esta sección se basa en el capítulo 11 en. ^[5]

Aplicaciones

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

Referencias

1. RJ Duffin y AC Schaeffer, Una clase de series de Fourier no armónicas, Transactions of the American Mathematical Society , vol. 72, núm. 2, págs. 341 {366, 1952. [En línea]. Disponible: https://www.jstor.org/stable/1990760
2. C. Heil, Introducción a la teoría básica: edición ampliada. Boston, MA: Birkhauser, 2010.
3. R. Balan, P. Casazza, C. Heil y Z. Landau, Densidad, sobrecompletitud y localización de fotogramas. I. teoría, Revista de análisis y aplicaciones de Fourier, vol. 12, núm. 2, 2006.
4. K. Grochenig, Fundamentos del análisis tiempo-frecuencia . Boston, MA: Birkhauser, 2000.
5. O. Christensen, Introducción a los marcos y las bases de Riesz. Boston, MA: Birkhauser, 2003.
6. [1], STA218, Nota de clase de minería de datos en la Universidad de Duke
7. MS Lewicki y TJ Sejnowski, Aprendizaje de representaciones sobrecompletas, Computación neuronal, vol. 12, núm. 2, págs. 337 {365, 2000.
8. P. Wolfe, S. Godsill y W. Ng, Selección y regularización de variables bayesianas para la estimación de superficies tiempo-frecuencia, JR Statist. Soc. B, vol. 66, núm. 3, 2004.