5
$\begingroup$

Since the Frobenius norm on matrices is generated by an inner product, solving the optimization/approximation problem of approximating an operator $X$ with a scalar multiple of another operator $Y$ $$\text{minimize:}\,\|X-\alpha Y\|_\mathsf{F}$$ has a closed form solution $\alpha = \frac{\langle X, Y \rangle}{\langle Y,Y \rangle}$ via an orthogonal projection.

What if I want to consider a non-Frobenius norm, specifically the standard operator norm / spectral norm / 2-norm? In other words, is there a closed form and/or efficient solution to the optimization problem $$\text{minimize:}\,\|X-\alpha Y\|_2$$ Since $\|A\|_2\leq \|A\|_\mathsf{F}$ for all $A$, solving the Frobenius version would provide an upper bound for the operator norm approximation. Is this approximation decent?

It feels like you could frame this problem as a semidefinite program under the self-adjoint assumption, but a closed form solution would be more optimal.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ The value for the Frobenius approximation can be about $\sqrt n$ off the true minimum for $n\times n$ matrices (consider $X=\operatorname{diag}(1,0,\dots,0)$ and $Y=\operatorname{diag}(1,a,\dots,a)$ with $a\approx n^{-1/2}$). An exact explicit formula for the minimizer is certainly out of question. The rest depends on how much you are willing to settle with. $\endgroup$
    – fedja
    Commented Jun 10, 2017 at 10:10
  • 3
    $\begingroup$ A simple SDP formulation is: \begin{equation*} \min_{a,t}\quad t\quad \text{s.t.}\quad\begin{bmatrix}tI & X-aY\\ (X-aY)^* & tI \end{bmatrix} \succeq 0. \end{equation*} $\endgroup$
    – Suvrit
    Commented Jun 10, 2017 at 13:33
  • $\begingroup$ Thanks to you both! In my specific application, $X=I$ and $Y$ is positive definitie. I'm trying to make $I-\alpha Y$ the optimal contraction under a submultiplicative norm. Looking into the $\|A\|_2 \leq \|A\|_\mathsf{F} \leq \sqrt{n}\|A\|_2$ bound, I can ensure that $\|A\|_\mathsf{F} \leq 1$ if the condition number $\kappa(Y) < \frac{1 + n^{-1/2}}{1 - n^{-1/2}}$. That's probably good enough as a start. $\endgroup$
    – Conner DiPaolo
    Commented Jun 10, 2017 at 19:32
  • 3
    $\begingroup$ But in this special case, minimizing $\|I-aY\|$ is the same as minimizing $\|I-aD\|$ where the $D$ is the diagonal of eigenvalues of $Y$; and the minimum of this problem is trivial! $\endgroup$
    – Suvrit
    Commented Jun 10, 2017 at 20:06

0

Reset to default

You must log in to answer this question.