Algoritmo para encontrar una base orthogonal (ortogonal a un vector dado)

Question

Deje $K$ ser un entero dado, con $K$ incluso (y "grande"). Deje $\mathbf{v} \in \mathbb{R}^{K \times 1}$ ser un determinado distinto de cero (columna) del vector. Escribe una (posiblemente eficaz) algoritmo para la construcción de una matriz de $\mathbf{B} \in \mathbb{R}^{K \times K-1}$ como que: $(1)$ la columna de vectores de $\mathbf{B}$ son ortogonales a cada uno de los otros; $(2)$ $\mathbf{B^T v} = \mathbf{0}$, donde $^T$ denota la transpuesta y $\mathbf{0}$ a ((K-1)-dimensional) vector de ceros.

Denotando con $\mathbf{b}_i$, $i=1,\dots,K-1$, el $i$-ésima columna de a $\mathbf{B}$, el primer requisito puede ser reescrita como: $\mathbf{b}_i^T \mathbf{b}_j = 0$$i \neq j$.

Esencialmente, el problema pide escribir un algoritmo para encontrar una base ortogonal para el complemento ortogonal de la (mono-dimensional) el espacio recorrido por $\mathbf{v}$. El algoritmo escrito en pseudocódigo (o en MATLAB o en C-como código). El algoritmo toma en la entrada el vector $\mathbf{v}$ y el entero $K$; su resultado es la matriz $\mathbf{B}$.

Nota: el algoritmo no puede hacer un "azar" prueba y error", es decir, generar un vector aleatorio, probar si es ortogonal a $\mathbf{v}$ y a la que anteriormente se encuentran las columnas de a $\mathbf{B}$, descartar si no, memorizar si es. Este es un explícitamente prohibido por fuerza bruta enfoque. Sin embargo, sí está permitido hacer esto como una etapa de inicialización, es decir, para la primera columna de la matriz o como una "estimación aleatoria" en el inicio, si es necesario para ello debe surgir. La "normalidad", es decir, la búsqueda de una base ortonormales, no es necesario. Comprobación de entrada (por ejemplo, la comprobación de si $K$ es un entero par) no es necesario.

EDIT: Mis pensamientos e intentos anteriores: El problema es esencialmente de una aplicación de Gram-Schmidts orthonormalization proceso. Sin embargo, no puede simplemente ser utilizado como se ha indicado, debido a que las bacterias Gram-Schimdts teorema supone empezar con una base (que no tenemos). Lo que realmente podemos construir es un sistema generador de vectores, es decir, $\mathbf{v}, e_1, \dots, e_K$ donde $e_i$ indica el $i$-th canónica de la base vectorial.

Ya he implementado Gram-Schmidts, prestando atención a numérica de problemas. El problema es de un ligero generalización del proceso, en el que no se empiece con una base, pero con un sistema generador, encontrar una base adecuada en el conjunto (no sé cómo hacerlo), el cual debe contener $\mathbf{v}$ como su primer elemento y, a continuación, aplicar Gram-Schimdts proceso.

P. S. Cualquier ayuda es muy apreciada, y yo no soy maestro de álgebra lineal, especialmente numérica de las implementaciones. Gracias.

Answer 1

Por cierto, que probablemente sea mucho más simple y eficiente para calcular su matriz $B$ aquí es sólo el uso de una sola Familia en la reflexión. Considere la posibilidad de $w=v\pm\|v\|_2e_1$ (el signo "$\pm$" por lo general es elegido para ser el mismo que en el primer componente en $v$ desde numérico razones). A continuación, establezca $Q=I-2ww^T/w^Tw$. Desde $Qv=\mp\|v\|_2e_1$ (dependiendo de la elección de la señal en $w$), tenemos $v=\mp\|v\|_2Qe_1$ (multiplicar por $Q^T=Q$). Esto significa que $v$ es un escalar varios de la primera columna (fila) de la matriz ortogonal $Q$. Deje $Q=[q_1,\ldots,q_K]$. De ello se desprende que $q_i^Tv=0$$i=2,\ldots,K$. Por lo tanto $B=[q_2,\ldots,q_K]$ satisface $B^Tv=0$$B^TB=I$.

En contraste a la $O(K^3)$ complejidad de las bacterias Gram-Schmidt enfoque (que por supuesto es de aplicación general para calcular ortonormales base para cualquier conjunto dado de vectores), de esta manera se consigue su $B$ $O(K^2)$ operaciones si usted necesita la matriz completa explícitamente calculadas o $O(K)$ si es suficiente con tener implícitamente representados por $w$.

Answer 2

Ejecutar Gram Schmidt orthogonalization sobre los vectores $v,e_1,...,e_K$ (ignorar una de las reducciones como debe ser cero o cerca de cero si los números son un problema), para obtener el $v_1,...,v_K$. A continuación, vamos a $B= \begin{bmatrix} v_2 \cdots v_K \end{bmatrix}$.

Detalles:

Por $e_k$ me refiero a que el vector de ceros con un uno en la $k$th posición. Tenga en cuenta que $e_1,...,e_K$ constituye una base para $\mathbb{R}^K$.

Deje $u_1 = v, u_k = e_{k+1}$$k=1,...,K$. Tenga en cuenta que $u_1,...,u_{K+1}$ es un sistema generador, pero no es una base.

A continuación, el algoritmo (esto es teórico, en una situación práctica de la comparación en el Paso 3 sería reemplazado por algo como $\|w_i\| < \epsilon$) se ve así:

1. $v_1 = {u_1 \over \|u_1\|}$, $i=2$
2. $w_i = u_i - \sum_{j=1}^{i-1} v_j^T u_i$
3. si $w_i \neq 0$ entonces $v_i = { w_i \over \|w_i\|}$ else $v_i = 0$
4. $i \leftarrow i+1$ si $i \le K+1$ goto Paso 2

Esta es básicamente la de Gram Schmidt algoritmo, a excepción de uno de los $v_i$s será igual a cero.

Por construcción, $\operatorname{sp} \{ u_1,...,u_i \} = \operatorname{sp} \{ v_1,...,v_i \}$, por lo tanto el conjunto final tendrá una duración de $\mathbb{R}^K$ (desde $u_2,...,u_{K+1}$ es una base). En consecuencia, exactamente una de las $v_i$s será igual a cero.

También por la construcción, $v_j^T v_i = 0$ todos los $j<i$, e $\|v_i\| = 1$ todos los $i$ a excepción de uno. Deje $v'_i, i=1,...,K$ ser el cero $v_i$s.

Ahora vamos a $B = \begin{bmatrix} v'_2 \cdots v'_K \end{bmatrix}$ y tenga en cuenta que $B^T v'_1 = 0$, y desde $v = \|v\| v'_1$, estamos acabados.