Find cross product of other part of orthogonal linear transformation of matrix

Question

Say that I know a dense matrix $Y\in\mathbb{R}^{n\times r}$. Further, let $Q\in\mathbb{R}^{n \times n}$ be an orthogonal matrix and $Q^\top Y = (C^\top, D^\top)^\top$ be two dense matrices such that $C\in\mathbb{R}^{p\times r}$ and $D\in\mathbb{R}^{(n - p)\times r}$ where $n \gg p \geq r$.

Can I determine the $r\times r$ matrix $D^\top D$ if I know $Y$ and $C$ but not $Q$? Further, can this easily be computed?

---

Motivation

The questions are posted above. I include this section to describe why I end up knowing $Y$ and $C$ but not $Q$ and $D$. It may be that I have a computed a quantity which makes it easy to find $D^\top D$ which I did not include in the information above. This is the second reason I include this part.

I want to solve

$$\underset{F}{\text{argmin}}\, \lVert Y - XF \rVert^2_2$$

where $X\in\mathbb{R}^{n\times p}$ and $F\in \mathbb{R}^{p\times r}$. One way to do this is to form a QR-decomposition $X=QR=Q(\bar{R}^\top, 0^\top)^\top$. Let $Q^\top Y=(C^\top, D^\top)^\top$. Then the solution is $\bar{R}F=C$. Further, I need $D^\top D$ later.

I want to do this in parallel as in the uni-variate case in

Wood, S. N., Goude, Y., & Shaw, S. (2015). Generalized additive models for large data sets. Journal of the Royal Statistical Society: Series C (Applied Statistics), 64(1), 139-155.

since it just requires a stanard method to form the QR decomposition and is easy to implement. The idea is to separate the $n$ rows in to $m$ chunks. For each chunk of rows of $Y$ and $X$ compute the QR decomposition $X_i=Q_iR_i=(\bar{R}_i^\top, 0^\top)^\top$ and $Q_i^\top Y_i=(C_i^\top, D_i^\top)^\top$ for $i=1,\dots,m$. Then compute the QR decomposition of

$$ \begin{pmatrix} \bar{R}_1 \\ \bar{R}_2 \\ \vdots \\ \bar{R}_m\end{pmatrix} = \widetilde{Q}R = \widetilde{Q}\begin{pmatrix}\bar{R} \\ 0\end{pmatrix} $$

such that we have $\bar{R}$ and then use that

$$C = \widetilde{Q}^\top_{\cdot, 1:p} \begin{pmatrix} C_1 \\ C_2 \\ \vdots \\ C_m \end{pmatrix}$$

where $\widetilde{Q}_{\cdot, 1:p}$ only consist of the first $p$ columns of $\widetilde{Q}$. Thus, I can solve $\bar{R}F=C$, I have $Y$ and $C$ but I lack $D$ and $Q$.

Answer 1

Use that $D^\top D = Y^\top Y - C^\top C$. The former can be be computed in $O(r^2n)$ and the latter can be computed in $O(r^2p)$. It is easy to confirm e.g., with R as below

r <- 5
n <- 1000
p <- 8

qr. <- qr(matrix(rnorm(n * p), ncol = p))
Y   <-    matrix(rnorm(n * r), ncol = r)
Q_Y <- qr.qty(qr., Y)
C   <- Q_Y[1:p      , ]
D   <- Q_Y[(p + 1):n, ]

all.equal(crossprod(D), crossprod(Y) - crossprod(C))
#R> [1] TRUE

The reason is that

$$Y^\top Y = Y^\top Q^\top QY = C^\top C +D^\top D$$