Pregunta sobre la restricción en los mapas propios del laplaciano

Question

Al calcular los mapas propios del laplaciano, el documento original menciona la restricción $$y^TDy=1$$ como "elimina un factor de escala arbitrario en la incrustación". Lo que yo entiendo es que impide $y$ de que se convierta en algo arbitrario.

Sin embargo, ¿por qué no se puede utilizar simplemente $y^Ty=1$ para lograr el mismo objetivo? En otras palabras, ¿por qué $D$ ¿es necesario aquí? Gracias.

Answer 1

Aquí está la respuesta de mi asesor así como mi elaboración. Creo que es más fácil de entender y lo pongo aquí, esperando que pueda ser de ayuda:

La razón por la que los mapas propios laplacianos utilizan $y^TDy = 1$ como restricciones es que si se utiliza la forma normal de normalizar y como $y^Ty = 1$ el vector propio se concentrará en los vértices con grados altos. Utilizando $y^TDy = 1$ puede mitigar este problema y hacer $y$ más suave.

El "concentrado" aquí significa que el vector propio tendrá un número extremadamente grande en la posición correspondiente al vértice con alto grado.

A continuación, no se trata de una prueba completa, sino de una intuición:

Pensando en el eigenvector no trivial de $L$ . Comenzamos con el caso no ponderado. Consideremos que $v_1$ tiene un grado mayor que otros vértices. Para algún vector propio $u$ tenemos $$(Lu)_i = deg_i u_i \sum_{j\in adj(i)}u_j = \lambda u_i$$ Esto significa que

$$deg_iu_i deg_i\mathbb{E}[u_j] = \lambda u_i$$ donde $j$ son los índices adyacentes de $i$ . $$u_i\mathbb{E}[u_j]= \frac{\lambda u_i}{deg_i}$$ Observando la restricción que $u^T \boldsymbol 1 = 0$ Si consideramos el caso extremo de que el nodo i se conecta a todos los demás nodos (un grafo en estrella), tenemos $\lambda = deg_i + 1$ . En este sentido, para algunos $k$ que $d_k < d_i$ tenemos $$\mathbb{E}(adj(u_k)) = -\frac{deg_i + 1}{deg_k}u_k$$ Esto significa que $\mathbb{E}(adj(u_k))$ que está cerca de $u_i$ debería estar mucho más lejos de 0 que $u_k$ .

Answer 2

Hay varias razones por las que un positivo definido $D$ es útil. Por un lado, una mayor generalidad es atractiva, ¿no?

Pero en más situaciones, $D$ es esencial. La mejor manera de pensar es la siguiente. La cuestión de la optimización proviene de algún problema "físico" natural en el que se plantea la cuestión del mínimo o del máximo sujeto a la restricción de que el vector $v$ (que representa la variación independiente) es de longitud unitaria, sí, para limitar la magnitud. En este punto, puede que ni siquiera haya matrices en la pregunta.

Sin embargo, luego viene la cuestión de expresar el problema en el espacio de los componentes. Para trasladar el problema al espacio de componentes, hay que elegir una base. En el espacio de componentes, el producto interior $(u,v)$ se expresa mediante el producto matricial $x^TDy$ donde $D$ es la matriz simétrica definida positiva que representa ese producto interior con respecto a la base elegida. La condición $(v,v)=1$ se convierte en $y^T Dy=1$ . Y, a menos que la base elegida sea ortonormal con respecto al producto interior en cuestión, $D$ no es la matriz identidad.

Como regla general, la mayoría de las cosas del álgebra lineal empiezan a tener sentido cuando se reconstruye el problema físico del que proceden.