5
$\begingroup$

Let $X=\lambda_0u_0v_0^T\in\mathbb{R}^{n\times n}$ be a rank 1 matrix where $\lambda_0\in\mathbb{R}$, $u_0,v_0$ are of unit Euclidean norm. What is the solution of the following problem? $$\hat{X}=\arg\min_{\substack{Y:Y=aU\\U\in O(n)\\a\in\mathbb{R}}}\|Y-X\|_F^2$$ where $U$ is orthogonal and $\|\|_F$ is the Frobenius norm. In other words, what is the best scaled orthogonal approximation of rank 1 matrix?

$\endgroup$
  • 2
    $\begingroup$ Just an attempt at a solution... You can assume WLOG that $X$ has only one nonzero entry $X_{11}>0$ by taking its SVD; then I'd guess that the minimizer is $\frac{\|X\|}{n} I_n$, and I would suggest looking into Weyl's inequalities for singular values (Exercise 22 here) to prove it. $\endgroup$ – Federico Poloni Jun 10 at 22:18
  • 2
    $\begingroup$ Isn't this an instance of the orthogonal Procrustes problem? $\endgroup$ – Rodrigo de Azevedo Jun 11 at 6:33
  • 2
    $\begingroup$ @RodrigodeAzevedo No, because of the $a$ term. But I guess that one can solve the problem for every fixed $a$ using the orthogonal Procrustes result, and then take the minimum of the resulting single-variable function. $\endgroup$ – Federico Poloni Jun 11 at 6:48
4
$\begingroup$

As suggested by Federico Poloni in a comment, it suffices via the SVD to consider the case when $X$ has $x_{1,1} > 0$ and $x_{i,j} = 0$ when $(i,j) \neq (1,1)$. Then for any orthogonal matrix $U$ with columns $\mathbf{u}_1,\ldots,\mathbf{u}_n$ and scalar $a \in \mathbb{R}$ we have \begin{align*} \|X - aU\|_F^2 & = \|x_{1,1}\mathbf{e}_1 - a\mathbf{u}_1\|^2 + \sum_{j=2}^n\|a\mathbf{u}_j\|^2 \\ & = \big(x_{1,1}^2 - 2ax_{1,1}u_{1,1} + a^2\big) + \big(\sum_{j=2}^na^2\big) \\ & = x_{1,1}^2 - 2ax_{1,1}u_{1,1} + na^2, \end{align*} where $\mathbf{e}_1 \in \mathbb{R}^n$ is the first standard basis vector. There is only one term in this expression that depends on $U$ at all, so (for any given value of $a$) it is minimized when we make $u_{1,1}$ as large as possible (i.e., $u_{1,1} = 1$). The remaining columns of $U$ are arbitrary (but of course must be orthogonal to the first column $\mathbf{e}_1$).

Our goal is then to minimize \begin{align*} x_{1,1}^2 - 2ax_{1,1} + na^2, \end{align*} which is a quadratic in $a$ with vertex (i.e., minimum) at $a = x_{1,1}/n$.

$\endgroup$

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.