How to solve the following problem explicitly? I mean closed form solution if possible.
$\min_{M} \|M\ a-b\|_2$
subject to :
$\|M\|_{\infty}<1$ (maximum singular value)
where $M$ is a square matrix and a and b are given vectors.
I tried to convert it to sdp like $MM^∗−I<0$ and try to setup the dual problem but I'm not sure if this problem has a dual form or not.
We want to minimize $\|Ma-b\|_2^2 = \displaystyle\sum_{i = 1}^{n}\left[\sum_{j = 1}^{n}(m_{ij}a_j) - b_i \right]^2$
subject to the constraint $\|M\|_{\infty} \le 1$, i.e. $\displaystyle\sum_{j = 1}^{n}|m_{ij}| \le 1$ for all $i$.
Let $k = \text{argmax}_{1 \le j \le n}|a_j|$. Split the minimization problem into $n$ problems (one for each $i$).
If $|b_i| \le |a_k|$, then we can set $m_{ik} = \dfrac{b_i}{a_k}$ and $m_{ij} = 0$ for $j \neq k$.
Then, $\displaystyle\sum_{j = 1}^{n}|m_{ij}| = |m_{ik}| = \dfrac{|b_i|}{|a_k|} \le 1$ and $\displaystyle\sum_{j = 1}^{n}m_{ij}a_j = m_{ik}a_k = b_i$.
Therefore, the constraint is satisfied and $\displaystyle\left[\sum_{j = 1}^{n}(m_{ij}a_j) - b_i \right]^2 = 0$ is minimized.
If $|b_i| > |a_k|$, then $\displaystyle\left|\sum_{j = 1}^{n}m_{ij}a_j\right| \le \sum_{j = 1}^{n}|m_{ij}||a_j| \le |a_k|\sum_{j = 1}^{n}|m_{ij}| \le |a_k|$.
Therefore, $\displaystyle\left[\sum_{j = 1}^{n}(m_{ij}a_j) - b_i \right]^2 \ge (|a_k|-|b_i|)^2$. If we set $m_{ik} = \text{sign}\dfrac{b_i}{a_k}$ and $m_{ij} = 0$ for $j \neq k$, then the minimum is achieved and $\displaystyle\sum_{j = 1}^{n}|m_{ij}| = |m_{ik}| = 1$.
Therefore, one matrix $M$ which minimizes $\|Ma-b\|_2$ subject to $\|M\|_{\infty} \le 1$ is $M = (m_{ij})$ where $$m_{ij} = \begin{cases}\dfrac{b_i}{a_k} & j = k \ \text{and} \ |b_i| \le |a_k| \\ \text{sign}\dfrac{b_i}{a_k} & j = k \ \text{and} \ |b_i| > |a_k| \\ 0 & j \neq k\end{cases}$$
Please note that this matrix isn't necessarily the only matrix which minimizes $\|Ma-b\|_2$. This is just a matrix which is easily shown to minimize $\|Ma-b\|_2$.
Also, if you require $\|M\|_{\infty} < 1$ (strict inequality) then there is not necessarily a minimum since the set of matrices $M$ for which $\|M\|_{\infty} < 1$ is not a closed set. However, you can perturb the entries of the above matrix slightly to get $\|M\|_{\infty} < 1$ and a slightly larger value of $\|Ma-b\|_2$.