Optimization with rank constraint

Question

Following some problems I like to explore, I found myself looking at minimizing the following: $$ \min_{B \text{ with rk}(B)<q} \sum_{i=1}^n (y_i-x_i^TBx_i)^2 $$ where $y_i \in \mathbb{R}, x_i \in \mathbb{R}^p-\lbrace 0 \rbrace, B \in \mathbb{R}^{p \times p}$. Would someone have any clue what are the known solutions to these kind of problems?

Answer 1

If you are looking for rank $0$ matrices, the only answer is $B=0$. If $x=0$ then the choice of $B$ does not matter, so we might as well take $B=0$. If you allow rank $1$ matrices, then the answer is $B=\alpha xx^T$, where $\alpha$ is chosen from the equation $y= x^TBx = \alpha \|x\|^4$, so that $\alpha = y/\|x\|^4$.

Answer 2

If $x$ is identically $0$ then you can take any matrix $B$ of rank $q-1$ - they are all optimal.

On the other hand, if $x$ is not identically $0$ then assume without loss of generality that the first component of $x$ is nonzero. Let $B = \mathrm{diag}((\alpha,1,1,\ldots,1,0,0,\ldots))$ be a diagonal matrix whose first entry is $\alpha$ and which is at most rank $q-1$, i.e., there are at least ($p-(q-1)$) entries equal to $0$.

We have $$x^TBx = \alpha x_1^2 + x_2^2 +\ldots +x_{q-1}^2$$

Since $\alpha$ is arbitrary, you can make it as big as or as small as necessary so that $\alpha x_1^2 = y-(x_2^2+x_3^2+\ldots +x_{q-1}^2)$ and the minimum is thus $0$. This is not the only solution but it attains the minimum ($0$).