Given $\boldsymbol{a}\in\mathbb{C}^{n},\ \boldsymbol{b}\in\mathbb{C}^{m}$ and $\delta>0$. Show how to solve following problems: $$\min_{\|E\|_{F}\leq\delta}\|E\boldsymbol{a}-\boldsymbol{b}\|_{2} \quad \text{and} \quad \max_{\|E\|_{F}\leq\delta}\|E\boldsymbol{a}-\boldsymbol{b}\|_{2}$$ over all $E\in\mathbb{C}^{m\times n}$ where $\|\cdot\|_{F}$ is Frobenius norm and $\|\cdot\|_{2}$ is vector $2$-norm.

I tried to apply SVD and QR factorization of $E$ but these methods seem to be useless because the variable is matrix $E$ and vectors are fixed, which is different from the least squares problem we usually deal with. Are there some powerful tools to solve it or some tricks should be apllied here?

Any help is appreciated.


Squaring the norms, we have

$$\begin{array}{ll} \text{minimize} & \| \mathrm X \mathrm a - \mathrm b \|_2^2\\ \text{subject to} & \| \mathrm X \|_{\mathrm F}^2 \leq \delta^2\end{array}$$

Vectorizing, we recognize this as a quadratically constrained quadratic program (QCQP)

$$\begin{array}{ll} \text{minimize} & \| ( \mathrm a^{\top} \otimes \mathrm I ) \, \mbox{vec} (\mathrm X) - \mathrm b \|_2^2\\ \text{subject to} & \| \mbox{vec} (\mathrm X) \|_2^2 \leq \delta^2\end{array}$$

which is convex. If we maximize instead, then the problem ceases to be convex.

  • $\begingroup$ I'm a novice in the field of optimization. So what's the definition of "vectorizing" and how come original problem $\|Xa-b\|_{2}^{2}$ is equivalent to $\|(a^{\top}\bigotimes I)vec(X)-b\|_{2}^{2}$? $\endgroup$ – Jay Oct 29 '16 at 21:07
  • $\begingroup$ @JacobZhang vectorization $\endgroup$ – Rodrigo de Azevedo Oct 29 '16 at 21:12
  • $\begingroup$ I found the definition of vectorizing from Wikipedia, Thanks. $\endgroup$ – Jay Oct 29 '16 at 21:13

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.