En el caso de una regularidad incluidos en la muestra, con valores escalares de la señal de $f$ sobre la línea real, podemos construir un discreto lineal operador $A$ tal que $A(f)$ aproxima $\partial^2 f / \partial x^2$. Una forma de interpretar este operador es a través de la descomposición espectral de la matriz correspondiente:
$$A = UVU^T.$$
Si nuestro operador $A$ ha precisión del espectro, a continuación, $U^T$ es, precisamente, la transformada de Fourier discreta de la matriz. Por lo tanto, podríamos calcular la transformada de Fourier de $x$ mediante el cálculo de todos los vectores propios de a $A$ y pegándolos en las columnas de $U$. Por supuesto, todos sabemos que hay una forma más rápida para hacerlo: el uso de la transformada rápida de Fourier (FFT).
Lo que acerca de una manera más general? En particular, considere la gráfica de Laplace $L=UVU^T$ que para un ponderado, grafo no dirigido en $n$ vértices es un $n \times n$ matriz con los pesos de los incidentes de los vértices de la diagonal y (el inverso aditivo de) total de incidentes de peso en la diagonal.
Pregunta:
Podemos transformar una señal de vértices en el espacio de frecuencia sin la computación de todo el espectro de $L$ (el uso de algo como la FFT)?
En particular, estoy interesado en el caso de que $L$ se aproxima a la de Laplace-Beltrami operador en algunos colector $M$ -- aquí vectores propios de a $L$ aproximado ortogonal eigenbasis de cuadrado integrable funciones en $M$. Sin embargo, los punteros a resultados cercanos (por ejemplo, de la FFT para la combinatoria gráfico Laplaciano) son apreciados.
