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?
$\begingroup$
$\endgroup$
3
-
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 PoloniJun 10, 2019 at 22:18
-
2$\begingroup$ Isn't this an instance of the orthogonal Procrustes problem? $\endgroup$– Rodrigo de AzevedoJun 11, 2019 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 PoloniJun 11, 2019 at 6:48
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
answered Jun 12, 2019 at 16:47