0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.