带非负约束的矩阵最佳秩1近似的数值求解方法问询
我正在寻找一种数值方法来求解以下优化问题，先明确一些符号定义：
- 设 $A\in\mathbb R^{m\times n}$ 是实矩阵，对于任意 $x,y\in\mathbb R^m$，$x\leq y$ 表示对所有 $i=1,\dots,m$ 都有 $x_i\leq y_i$
- 对任意矩阵 $B$，$| B |_F$ 是 Frobenius 范数，定义为 $| B |_F^2 := \operatorname{Tr}\left(B^T B\right)$，这里回顾迹的循环性质 $\operatorname{Tr}(AB) = \operatorname{Tr}(BA)$，且1×1矩阵的迹就是其唯一元素
我的目标问题是求解带约束的秩1近似：
$$
\min_{\substack{u\in\mathbb R^m,v\in\mathbb R^n\ 0\leq Av}} \left| A - u v^T \right|_F^2
$$
从实际应用场景来看，我们有 $m\ll n$（比如m是几百量级，n通常超过百万），我期望能得到类似PCA迭代计算的时间复杂度，大概是 $O(m^2n)$。另外我也对 $n<m$ 的情况略有兴趣。
初步思路：交替优化法
这个问题本身不是凸的，但在 $\mathbb R^m\times \mathbb R^n$ 的凸子集上是双凸的，所以我首先想到的是交替优化u和v。首先我把目标函数展开化简：
$$
\begin{align*}
| A - uv^T |_F^2 &= |A|_F^2 + \mathrm{Tr} (vuTuvT) - 2 \mathrm{Tr}(v u^T A)\
&= |A|_F^2 + vTvuTu - 2 u^T A v\
&= | A |_F2+|u|2\cdot |v|^2 - 2 u^T A v
\end{align*}
$$
对u求导得到 $2|v|^2u-2Av$，对v求导得到 $2|u|^2 v - 2 A^T u$。由于v有约束 $0\leq Av$，我需要构造拉格朗日函数并写出KKT条件（固定u时这些条件是充分的，但全局不一定），设拉格朗日乘子 $\mu\in\mathbb R^m$，KKT条件如下：
$$
\begin{cases}
2|u|^2 v - 2 A^T u-A^T\mu=0\
0\leq Av\
0\leq \mu\
\mu^TAv = 0
\end{cases}
$$
从这些条件能推出 $| v |^2u=Av$，但我没法直接解这个关于v的方程组，所以考虑转而去解它的Wolfe对偶问题：
$$
\max_{v,\mu} | u |^2\cdot | v|^2-2 uTAv-\muTAv
$$
约束条件为 $2| u|^2\cdot v-2ATu-AT\mu=0$ 且 $\mu\geq 0$。解出v并代入优化表达式后，经过化简得到：
$$
\max_{\mu\geq 0} -(2u+\mu)^TM(2u+\mu)
$$
这等价于求解 $\min_{\mu\geq 0} (2u+\mu)M(2u+\mu)$，我后续打算单独针对这个子问题深入研究，等有结果后再整理整体内容。
另外，设 $A^\dagger\in\mathbb R^{n\times m}$ 是A的Moore-Penrose伪逆，其中 $A^\dagger A$ 和 $A A^\dagger$ 分别是投影到 $A^T$ 和A的列空间的投影矩阵。
已推导得到的几个结论
Fact 1: 原问题的解 $u,v$ 满足 $uv^T = 0$ 当且仅当 $\operatorname{span}(A) \cap [0,\infty[^m = { 0}$
证明：如果 $uv^T\neq0$，由KKT条件可得 $0\leq u=\frac{Av}{|\ v|^2}\in\mathrm{span}(A)\cap [0,\infty[^m$，且u≠0；反过来，如果存在 $0\neq a\in \mathrm{span}(A)\cap[0,\infty[^m$，取 $b=A^\dagger a \neq 0$，计算可得 $\left| A-\frac{abT}{|b|2} \right|_F^2 = | A |_F^2 - \frac{| a|^2}{| b|^2} <| A |_F^2$，因此 $uv^T\neq 0$。
Fact 2: 如果 $uv^T\neq 0$，则 $u\in \mathrm{span}(A)$ 且 $v\in\mathrm{span}(A^T)$，此外有 $u=A\frac{v}{| v|^2}$ 和 $v = AT\frac{2u+\mu}{2|u|2}$
证明：由KKT条件可直接得出。
Fact 3: 如果 $a$, $\sigma$, $b$ 是A的一个奇异三元组且满足 $0\leq a$，那么 $u=a$ 和 $v=\sigma b$ 满足所有KKT条件
证明：计算可得 $2| v|^2u-2Av = 2\sigma^2 a- 2 \sigma^2a=0$，取 $\mu=0$ 则 $2|u|^2 v - 2A^Tu=2\sigma b-2\sigma b=0$，同时满足 $0\leq \sigma^2 u = Av$。
备注：内容来源于stack exchange，提问作者P. Quinton
