How can I solve "average" best rank-$1$ approximation?

Question

Assume I want to minimise this

$$ \min_{x,y} \left\| A - x y^T \right\|_{\text{F}}^2$$

then I am finding best rank-$1$ approximation of $A$ in the squared-error sense and this can be done via the SVD, selecting $x$ and $y$ as left and right singular vectors corresponding to the largest singular value of $A$.

Now instead, is possible to solve the following for $b$ also fixed?

$$ \min_{x} \left\| A - x b^T \right\|_{\text{F}}^2$$

If this is possible, is there also a way to solve

$$ \min_{x} \left\| A - x b^T \right\|_{\text{F}}^2 + \left\| C - x d^T \right\|_{\text{F}}^2$$

where I think of $x$ as the best "average" solution between the two parts of the cost function?

I am of course longing for a closed-form solution but a nice iterative optimisation approach to a solution could also be useful.

Answer 1

This is a Convex Optimization Problem and you can easily solve it using CVX:

numRows = 5;

mA = randn([numRows, numRows]);
vB = randn([numRows, 1]);


cvx_begin('quiet')
    cvx_precision('best');
    variable vX(numRows)
    minimize( norm(mA - vB * vX.', 'fro') )
cvx_end

disp([' ']);
disp(['CVX Solution Summary']);
disp(['The CVX Solver Status - ', cvx_status]);
disp(['The Optimal Value Is Given By - ', num2str(cvx_optval)]);
disp(['The Optimal Argument Is Given By - [ ', num2str(vX.'), ' ]']);
disp([' ']);

If you formulate your expression using the Trace Operator you'll also be able to solve it easily in other simple methods.

Answer 2

$$\| \mathrm A - \mathrm x \mathrm b^{\top} \|_{\text{F}}^2 = \cdots = \| \mathrm b \|_2^2 \, \| \mathrm x \|_2^2 - \langle \mathrm A \mathrm b , \mathrm x \rangle - \langle \mathrm x , \mathrm A \mathrm b \rangle + \| \mathrm A \|_{\text{F}}^2$$

Taking the gradient of this cost function,

$$\nabla_{\mathrm x} \| \mathrm A - \mathrm x \mathrm b^{\top} \|_{\text{F}}^2 = 2 \, \| \mathrm b \|_2^2 \, \mathrm x - 2 \mathrm A \mathrm b$$

which vanishes at the minimizer

$$\mathrm x_{\min} := \color{blue}{\frac{1}{\| \mathrm b \|_2^2} \mathrm A \mathrm b}$$

Note that

$$\mathrm A - \mathrm x_{\min} \mathrm b^{\top} = \mathrm A - \mathrm A \left( \frac{ \,\,\,\mathrm b \mathrm b^{\top} }{ \mathrm b^\top \mathrm b } \right) = \mathrm A \left( \mathrm I_n - \frac{ \,\,\,\mathrm b \mathrm b^{\top} }{ \mathrm b^\top \mathrm b } \right)$$

where

• $\frac{ \,\,\,\mathrm b \mathrm b^{\top} }{ \mathrm b^\top \mathrm b }$ is the projection matrix that projects onto the line spanned by $\mathrm b$, which we denote by $\mathcal L$.

• $\left( \mathrm I_n - \frac{ \,\,\,\mathrm b \mathrm b^{\top} }{ \mathrm b^\top \mathrm b } \right)$ is the projection matrix that projects onto the orthogonal complement of line $\mathcal L$.

Hence, the minimum is

$$\| \mathrm A - \mathrm x_{\min} \mathrm b^{\top} \|_{\text{F}}^2 = \left\| \mathrm A \left( \mathrm I_n - \frac{ \,\,\,\mathrm b \mathrm b^{\top} }{ \mathrm b^\top \mathrm b } \right) \right\|_{\text{F}}^2 = \color{blue}{\left\| \left( \mathrm I_n - \frac{ \,\,\,\mathrm b \mathrm b^{\top} }{ \mathrm b^\top \mathrm b } \right) \mathrm A^\top \right\|_{\text{F}}^2}$$

which is the sum of the squared $2$-norms of the projections of the rows of $\rm A$ (i.e., the columns of $\rm A^\top$) onto the orthogonal complement of line $\mathcal L$.

---

matrices rank-1-matrices

Answer 3

You already have solutions with CVX (convex optimization), but in fact you can solve this using simple ordinary linear least squares and representing matrix multiplication with Kronecker products. Let $M_E$ represent multiplication by $E$ (from the right) and $v_A,v_C,v_x$ be the respective vectorization of $A,C,x$ we can rewrite it:

$$\min_{v_x}\left\{\|v_A- M_{b^t}v_x\|_2^2 + \|v_C- M_{d^t}v_x\|_2^2\right\}$$

Which you can expand using $\|Y\|^2 = Y^TY$, then expand, differentiate, sum up and set derivative equal $0$ and solve.

You can read more about the details of the vectorization on Wikipedia entry Kronecker Products