Encontrar una matriz $Q \in \mathbb{R}^{d\times r}$ tal que $Q^\top Q=I_r$ y $(QQ^\top)_{ii}=h_{ii}$

Question

Dadas $\{h_{ii}\}_{i=1}^d$, donde $h_{ii}\in[0,1],$ y $\displaystyle\sum_{i=1}^d h_{ii}=r<d,$ existe una matriz $Q\in\mathbb{R}^{d\times r},$ s.t.

$$Q^\top Q=I_r, \qquad (QQ^\top)_{ii}=h_{ii}?$$

Answer 1

(Para mayor comodidad, escribo $h_i$ en lugar de $h_{ii}$.)

Usted puede comenzar con $Q=\pmatrix{I_r\\ 0}$. La idea es fijar las entradas de la diagonal de a $QQ^T$ uno por uno, mediante la aplicación de las rotaciones de Givens a $Q$ de forma recursiva. Más concretamente, supongamos que en algún momento, tenemos $Q^TQ=I_r$ y $$ Q^T=\left[\begin{array}{c|c}P&\ast \\ \hline\ast&\begin{matrix}q_{k+1}\\ &\ddots\\ &&q_d\end{de la matriz} \end{array}\right],\etiqueta{$\dagger$} $$ donde las entradas de la diagonal de a $P$ son miembros de $\{h_1,\ldots,h_d\}$. Por el reetiquetado de la $h_i$s si es necesario, podemos asumir que se es $(h_1,\ldots,h_k)$. También suponga que la parte inferior derecha subblock de $QQ^T$ $(1)$ es una matriz diagonal $\operatorname{diag}(q_{k+1},\ldots,q_d)$ tal que

1. $\sum_{i=k+1}^dh_i=\sum_{i=k+1}^dq_i$,
2. $q_{k+1}\ge\cdots\ge q_s>h_{k+1}\ge\cdots\ge h_d>q_{s+1}\ge\cdots\ge q_d$ algunos $s$.

Ahora, tenga en cuenta que \begin{align} &\pmatrix{\cos t&-\sin t\\ \sin t&\cos t} \pmatrix{q_s\\ &q_{s+1}} \pmatrix{\cos t&\sin t\\ -\sin t&\cos t}\\ =&\pmatrix{q_s\cos^2 t+q_{s+1}\sin^2 t&\ast\\ \ast&q_s\sin^2 t+q_{s+1}\cos^2 t}, \end{align} Por lo tanto, mediante la aplicación de una adecuada rotación de Givens $R$ $s$- th y $(s+1)$-th filas de $Q$, que puede dar vuelta a una de las $s$-th o $(s+1)$-ésimo de la diagonal de entradas de $(RQ)(RQ)^T$ en cualquier combinación convexa de $q_s$$q_{s+1}$. En particular,

• si $q_s-h_{k+1}<h_d-q_{s+1}$, hagamos el $s$-ésimo de la diagonal de la entrada de $(RQ)(RQ)^T$ hace $h_{k+1}$;
• si $q_s-h_{k+1}\ge h_d-q_{s+1}$ en lugar de eso, hagamos el $(s+1)$-ésimo de la diagonal de la entrada de $(RQ)(RQ)^T$ igual a $h_d$.

Tenga en cuenta que las entradas en $P$ no se ven afectados y todavía tenemos $(RQ)^T(RQ)=Q^TQ=I_r$. Realizar una más de permutación para mover el nuevo conjunto de la diagonal de la entrada a la posición $(k+1,k+1)$. Si la otra diagonal de la entrada de los involucrados en la rotación de transformar también es igual a algunos $h_i$, realice uno más de permutación que pase diagonal de la entrada a la $(k+2,k+2)$-ésima posición. La matriz resultante es de la forma $(\dagger)$ (sino $k$ es ahora incrementa por $1$ o $2$), con la parte inferior derecha subblock sigue siendo diagonal. Lo que es más importante, ya que la traza se conserva y debido a la forma en que establezca el nuevo $(k+1)$-ésimo de la diagonal de la entrada, las condiciones 1 y 2 en la de arriba también están satisfechos en la matriz resultante.

Así, hemos reducido la dimensión del problema por $1$ o $2$. Proceder de forma recursiva, se puede construir una matriz de $Q$ con columnas ortonormales, de manera que la diagonal de $QQ^T$ es una permutación de $(h_1,\ldots,h_d)$. Ahora, aplique una final de la permutación de las filas de $Q$, de modo que la diagonal de $QQ^T$ es exactamente $(h_1,\ldots,h_d)$.

Answer 2

mal

Demostrar eso si $$\left(QQ^{\top}\right)_{ii}=h_{ii},$$ then $$Q^{\top}Q=I_r.$$ It's clear that $$\text{rank}\left(QQ^{\top}\right)=\text{rank}(Q)\leq r.$$ Notice that $$\left(I_d-QQ^{\top}\right)_{ii}=1-h_{ii}\in[0,1]$$ and $$\sum_{i=1}^d(1-h_{ii})=d-r,$$ hence $$\text{rank}\left(I_d-QQ^{\top}\right)\leq d-r.$$ It follows that $$\text{rank}\left(QQ^{\top}\right)+\text{rank}\left(I_d-QQ^{\top}\right)\leq d.$$ However, $$\text{rank}\left(QQ^{\top}\right)+\text{rank}\left(I_d-QQ^{\top}\right)\geq\text{rank}(I_d)=d,$$ hence $$\text{rank}\left(QQ^{\top}\right)+\text{rank}\left(I_d-QQ^{\top}\right)=d.$$ It follows that $QQ^{\top}$ is idempotent, hence it's eigenvalues are either $0$ or $1.$ However, $$\sum_i\lambda_i=\text{tr}\left(QQ^{\top}\right)=\sum_{i=1}^dh_{ii}=r,$$ hence, using the singular value decomposition, $$Q=U\Sigma V^{\top}$$ where $$\Sigma=\begin{pmatrix} I_r\\ 0 \end{pmatrix}.$$ Now, $$Q^{\top}Q=V\Sigma^{\top}\Sigma V^{\top}=VI_rV^{\top}=VV^{\top}=I_r.$$

Answer 3

Suponiendo que el Hadamard Conjetura es verdadera, si $d$ es un múltiplo de a $4$, luego una fina $d \times r$ matriz que satisface las restricciones dadas está dada por

$$\boxed{\mathrm Q := \frac{1}{\sqrt d} \mathrm H_d^{\top} \mathrm S_r}$$

donde

• $\mathrm H_d \in \{\pm 1\}^{d \times d}$ es una matriz de Hadamard. Por lo tanto, el $d$ filas de $\mathrm H_d$ son ortogonales, es decir, $$\mathrm H_d \mathrm H_d^{\top} = d \, \mathrm I_d$$

• $\mathrm S_r$ es una fina capa de $d \times r$ matriz cuyas $r$ columnas son elegidos de las $d$ columnas de la $d \times d$ matriz identidad. Por lo tanto, el $r$ columnas de $\mathrm S_r$ son ortonormales, es decir,

$$\mathrm S_r^{\top} \mathrm S_r = \mathrm I_r$$

Por lo tanto,

$$\mathrm Q^{\top} \mathrm Q = \frac{1}{d} \mathrm S_r^{\top} \mathrm H_d \mathrm H_d^{\top} \mathrm S_r = \frac{d}{d} \mathrm S_r^{\top} \mathrm S_r = \mathrm I_r$$

como se desee. Deje $\mathrm e_k$ $\mathrm h_k$ el valor del $k$-th columnas de $\mathrm I_d$$\mathrm H_d$, respectivamente. Por lo tanto,

$$\mathrm e_k^{\top} \mathrm Q \mathrm Q^{\top} \mathrm e_k = \| \mathrm Q^{\top} \mathrm e_k \|_2^2 = \frac 1d \| \mathrm S_r^{\top} \mathrm H_d \mathrm e_k \|_2^2 = \frac 1d \| \mathrm S_r^{\top} \mathrm h_k \|_2^2 = \frac 1d \sum_{k=1}^r (\pm 1)^2 = \frac rd < 1$$

para todos los $k \in \{1,2,\dots,d\}$, como se desee. Tenga en cuenta que hemos utilizado el hecho de que las entradas de $\mathrm h_k$$\pm 1$.

Si $d$ es una potencia de $2$, $\mathrm H_d$ puede ser construido de forma recursiva mediante la Sylvester construcción

$$\mathrm H_{2k} = \begin{bmatrix} \mathrm H_k & \mathrm H_k\\ \mathrm H_k & -\mathrm H_k\end{bmatrix} \qquad \qquad \qquad \mathrm H_1 = 1$$

lo que se construye (simétrica) Walsh matrices. Si $d$ es no un poder de $2$, podemos utilizar el Paley de la construcción en su lugar.

Answer 4

EDIT: Esta respuesta es errónea; la condición de $\sum h_{ii}=r$ no está satisfecho.

---

He estado pensando mucho sobre esto, pero hay algo. Deje $\{f_j\}_{j=1}^d$ ser la base canónica de $\mathbb{R}^d$. Entonces

$$h_{jj}=f_j^TQQ^Tf_j={\left(Q^Tf_j\right)}^T\left(Q^Tf_j\right)=\lVert Q^Tf_j\rVert^2$$

Por lo tanto, $h_{jj}$ es el cuadrado de la norma de $Q^T$'s $j$-ésima columna, o en otras palabras, $Q$'s $j$-ésima fila. En particular, $h_{jj}=0$ si y sólo si $Q$'s $j$-ésima fila es $0$.

Si al menos $d-(r-1)$ de la $h_{jj}$'s son cero, el número de distinto de cero filas en $Q$ menos de $r$. En este caso, $\text{rank}(Q)<r$, lo que estaría en contradicción con $Q^TQ=I_r$.$^*$

Por lo tanto, la respuesta es "no siempre".

$^*$: Recordar que $\text{rank}(AB)\leq\min\{\text{rank}(A),\text{rank}(B)\}$ o que $\text{rank}(A)=\text{rank}(A^T)=$ $\text{rank}(AA^T)=\text{rank}(A^TA)$.