Aproximación óptima de la forma cuadrática

Question

Dejemos que $\mathbf{x}\in\Bbb{R}^n$ y $A\in\Bbb{S}_{++}^n$ , donde $\Bbb{S}_{++}^n$ denota el espacio de simetría positiva definida $n\times n$ matrices reales. Además, dejemos que $Q\colon\Bbb{R}^n\to\Bbb{R}_{+}$ sea la forma cuadrática dada por $$ Q(\mathbf{x})=\mathbf{x}^\top A\mathbf{x}\geq0. $$ Me gustaría hacer una aproximación $Q(\mathbf{x})$ por un múltiplo escalar de la norma euclidiana al cuadrado de $\mathbf{x}$ Es decir $$ Q(\mathbf{x})\approx c \lVert\mathbf{x}\rVert^2,\quad c>0. $$ Si $A$ es un múltiplo de la matriz identidad (de orden $n$ ), es decir $A=aI_n$ , $a>0$ entonces $c=a$ y $Q(\mathbf{x})=a\lVert\mathbf{x}\rVert^2$ . En este caso no tenemos ninguna aproximación sino una igualdad estricta.

Por otro lado, ¿es $A\neq aI_n$ podríamos aproximar la forma cuadrática utilizando la media de los valores propios de $A$ ya que se sostiene que $$ \lambda_{min}(A)\lVert\mathbf{x}\rVert^2\leq Q(\mathbf{x})\leq\lambda_{max}(A)\lVert\mathbf{x}\rVert^2, $$ es decir, $$ Q(\mathbf{x})\approx\frac{1}{n}\sum_{i=1}^{n}\lambda_{i}(A)\lVert\mathbf{x}\rVert^2, $$ y por lo tanto $c=\frac{1}{n}\sum_{i=1}^{n}\lambda_{i}(A)$ .

¿Hay alguna manera de encontrar un $c$ tal que la aproximación de $Q(\mathbf{x})$ es óptimo (por satisfacer algún criterio)?

Answer 1

Desde $$\mathbf{Q}(\mathbf{x})=\sum_{i=1}^n \sum_{j=1}^n a_{ij}x_ix_j$$

Podemos representar $\mathbf{Q}(\mathbf{x})$ como un vector $\mathbf{q} \in \mathbb{R}^d,d=\frac{n+n^2}{2}$ con las funciones de base cuadrática $\{x_1^2,x_1x_2,...,x_n^2\}$ :

$$\mathbf{Q}(\mathbf{x})=a_{11}x_1^2+2a_{21}x_1x_2+....+a_{nn}x_{n}^2$$ $$\mapsto \mathbf{q}:=(a_{11},2a_{21},....,a_{nn})$$

También podemos representar $||\mathbf{x}||^2$ en este espacio:

$$||\mathbf{x}||^2 = x_1^2+x_2^2+...+x_n^2$$ $$\mapsto \mathbf{v}:=(1,0,0,0,..,1,0,0,0,...,0,1)$$

Ahora, vamos a intentar minimizar la norma euclidiana al cuadrado de la diferencia entre $c\mathbf{v}$ y $\mathbf{q}$ :

$$\min_c L(c),\;\; \mathrm{where}\; L(c):=||\mathbf{q}-c\mathbf{v}||^2$$

Un (muy) poco de álgebra lo demuestra:

$$L(c)= \sum_{i=1}^n (a_{ii}-c)^2 + \sum_{i\neq j}a_{ij}$$

Será una función convexa de $c$ Así que simplemente tomamos la derivada y la ponemos a 0:

$$\frac{d}{dc} L(c) = -2\sum_{i=1}^n (a_{ii}-c)=0 \implies c=\frac{1}{n}\sum_{i=1}^n a_{ii}$$

Por lo tanto, podemos establecer $c$ a la media de la traza de A:

$$c=\frac{Tr(A)}{n}$$

Answer 2

Adopté un enfoque probabilístico del problema. Quería decir algo así como que si eliges un "vector aleatorio" $x$ entonces $Q(x)$ será "típicamente" $c\|x\|^2$ . Decidí que típicamente sería el valor esperado de $Q(x)$ . Así que quiero mostrar $$E[Q(X)] = c\|X\|^2$$ para algunos $c$ .

Esto también requiere una distribución para un vector aleatorio $X$ . Me gustaría decir que se eligió uniformemente de $\mathbb{R}^n$ pero no existe tal medida. En su lugar, consideraré opciones de vectores que son uniformes en la esfera unitaria $S^n$ y tener la longitud dada por alguna otra distribución. Resulta que el resultado es independiente de la otra distribución. Buscaré entonces una "c" s.t. $$E[Q(X)] = c$$ donde $X$ se elige de la esfera unitaria.

Es un teorema que si $X_i$ se eligen independientemente de una distribución normal $N(0, 1)$ entonces el vector con componentes $$Y_i = \frac{X_i}{\sqrt{\sum_{i=1}^nX_i^2}} $$ se distribuye uniformemente en la esfera.

Tomando $\{e_i\}$ sea una base propia para $Q$ podemos escribir su valor en un vector $Y$ como $$Q(Y) = \sum_{i=1}^n \lambda_i Y_i^2$$ Entonces $$E[Q(Y)] = E[\sum_{i=1}^n \lambda_i Y_i^2] = \sum_{i=1}^n \lambda_i E[Y_i^2]$$

Ahora, $E[\sum_{i = 1}^n Y_i^2] = 1$ así que por simetría $E[Y_i^2] = \frac{1}{n}$ . Así llegamos a $$E[Q(Y)] = \frac{1}{n}\sum_{i=1}^n \lambda_i$$

Un buen efecto secundario de este enfoque es que realmente tenemos la distribución completa de la variable aleatoria $Q(Y)$ que es $$Q(X) = \frac{\sum_{i=1}^n \lambda_i X_i^2}{\sum_{i=1}^nX_i^2}$$ que es válido siempre que el vector $X$ se elige de una densidad simétrica bajo rotaciones. A partir de ahí se puede analizar la precisión del estimador.

Answer 3

Aunque @Bey tenía razón, podemos enunciar un resultado más general en un lenguaje natural para las matrices.

Consideremos el Schatten $p$ -norma con la $k$ mayor valor singular para $p = 1$ o $p = 2$ . Entonces, después de cambiar a una base ortonormal de $A$ podemos suponer $A$ para ser diagonal y el problema se reduce a $\ell_p$ aproximación de $k$ mayores valores Eigen de $A$ por un escalar $c$ . En caso de $p = 1$ la solución es la mediana de estas $k$ Valores propios. En el caso de $p = 2$ la solución es la media de estos $k$ Valores propios.

El cómputo sólo es "fácil" en el caso expuesto por @Bey, es decir $k=n$ y $p=2$ .