Como parte de una serie de ejercicios que estoy haciendo ahora para matar el tiempo durante el brote de Covid-19 (y gracias a mi profesor de la Universidad) me topé con este problema:
Dejemos que $A:=(A_1|...|A_p)\in \mathbb{R}^{n\times p}$ donde los vectores horizontales $A_i\in \mathbb{R}^n$ se normalizan bajo $L_2$ norma. Sea $b\in col(A)$ , donde $col(A)$ denota los espacios abarcados por las columnas de la matriz $A$ y $\tilde{x}$ sea una solución del sistema lineal $Ax=b$ . Sea $I$ denotan el apoyo de $\tilde{x}$ , es decir, los índices de las filas, donde dicho vector tiene valores distintos de cero. Sea $A_I$ sea una matriz, compuesta por columnas $(A_i)_{i\in I}$ y $sign(x_I^*)$ sea un vector de valores dado por $sign(x_i^*)$ para cualquier $i\in I$ . Por $M(A)$ dejemos denotar $max_{i\neq j}\{|<A_i,A_j>|\}$ El objetivo es demostrar esta desigualdad: $$||x^*||_0 \leq (1+1/M(A))/2 \implies \forall j \notin I: |A'_JA_I(A'_IA_I)^{-1}sign(x^*_I)|\leq 1$$
Se dieron algunas pistas como las siguientes:
1) Demuestre el teorema del círculo de Gershgorin para valores propios reales. (Lo cual pude hacer)
2) Demuestre que el mayor valor propio de $(A'_IA_I)^{-1}$ es menor que $2/(M(A)+1)$
para lo cual presentaré mi razonamiento y el lugar donde me he quedado atascado:
Sabemos que $(A'_IA_I)^{-1}$ es $n\times n$ que es positiva definida y tiene valores propios reales. Así que a partir de 1) sabemos que cualquiera de sus valores propios cae en el intervalo dado como $[Q_{i,i}-\sum_{j\neq i}|Q_{i,j}|,Q_{i,i}+\sum_{j\neq i}|Q_{i,j}|]$ . Pero podemos ver fácilmente que $Q_{i,i}=<A_i,A_i>$ es por definición igual a 1, y para otros $Q_{i,j}=<A_i,A_j>$ . También sabemos que $ \forall i,j: |<A_i,A_j>|\leq M(A) $ . También $A'_IA_I$ sólo tiene valores propios positivos y los valores propios de $(A'_IA_I)^{-1}$ son iguales a $1/\lambda$ donde $\lambda$ es el valor propio de $A'_IA_I$ . Así que, de forma equivalente, tenemos que encontrar el valor propio más pequeño de $A'_IA_I$ y encontrar su límite inferior de 1). Pero aquí tengo un problema porque tengo tal sistema de desigualdades: $$1-\sum_{j\neq i} |<A_i,A_j>| \leq \lambda \leq 1+\sum_{j\neq i} |<A_i,A_j>|$$ o utilizando $M(A)$
$$1-kM(A) \leq \lambda \leq 1+kM(A)$$ donde la dimensión de $A'_IA_I$ es $k\times k$ desde donde no puedo llegar a la forma deseada.
3) Usa 2) para demostrar la desigualdad en el lado derecho de la implicación.
Aquí también me he atascado, ya que incluso asumiendo que 2) está probado, no puedo conectar cómo el límite en el valor propio podría ayudarme a probar la desigualdad dada, usando el lado izquierdo de la implicación, no importa lo mucho que trate de envolver mi mente en esto.
Agradecería cualquier ayuda, pista o dirección a seguir en esos casos, ya que estoy atascado en ellos desde hace unos 2 días y no puedo hacer ningún progreso hasta ahora. ¡Gracias de antemano!
