Max-norm optimization for robust matrix recovery (Q681486)

In order to recover an unknown matrix $M^0 \in \mathbb{R}^{d_1 \times d_2}$ based on some of its entries observed with noise, $\{Y_{i_t,j_t}\}_{t=1}^n$, the authors propose a hybrid estimator defined as the solution of the optimization problem \[ \begin{cases} \text{Minimize }\frac{1}{n} \sum_{t=1}^n (Y_{i_t,j_t} - M_{i_t,j_t})^2 +\lambda \|M\|_{\max} + \mu \|M\|_*, \\ \text{subject to } M \in \mathbb{R}^{d_1 \times d_2},\; \|M\|_\infty \leq \alpha, \end{cases} \] where $\|M\|_{\max}$, $\|M\|_*$ and $\|M\|_\infty$ denote the max-norm, the nuclear norm and the elementwise $\infty$-norm of $M$, respectively, while $\lambda >0$ and $\mu \geq 0$ are tuning parameters. Efficient algorithms are provided along with numerical experiments on different datasets.