How to solve the constrained linear equations?

Question

$W \in \mathbb{R}^{n\times p}$, $a,b \in \mathbb{R}^{p\times 1}$, $K \in \mathbb{R}^{n\times n}$, $n<p$.

Here is the problem: $Wa = b$ with constraint $WW^T = K$ where K, a, b are given.

Since $n<p$, we have K full rank. How to analysis the existence of W or even compute the W? Can anyone give me a hint?

Answer 1

Suppose that $K^{-1} = LL^T$ is a Cholesky decomposition where $L$ is $n \times p$. Then we can rewrite $$ Wa = b, \quad WW^T = K \implies\\ Wa = b, \quad (LW)(LW)^T = I \implies\\ (LW)a = (Lb), \quad (LW)(LW)^T = I. $$ That is, if we make the substitution $M = LW$ and $y = LB$, then your problem is equivalent to solving $$ Ma = y, \qquad MM^T = I. $$ Notably, the constraint that $MM^T = I$ simply means that the rows of $M$ are orthonormal. One approach to construct such an $M$ is as follows:

• Find any matrix satisfying $PP^T = I$ for which $\|Pa\| = \|y\|$
• Find an orthogonal matrix $U$ satisfying $U(Pa) = y$
• Take $M = UP$

Notably, the reframed problem will have a solution if and only if $\|y\| \leq \|a\|$.