Finding the extremal singular triplet $(σ, u, v)$ of a generic real $m×n$ matrix $A$ can be formalized as a nonconvex quadratically-constrained quadratic program (QCQP):
$$σ = \max_{u,v}\quad u^⊤ A v \qquad\text{s.t.}\qquad ‖u‖_2 = 1 \text{ and } ‖v‖_2 =1$$
Or, in standard form: $\max\limits_{z} \frac{1}{2} z^⊤ Q z$ with $z^⊤P_kz + ρ_k = 0$ for $k=1…K$.
$$ σ = \max_{u,v}\quad \frac{1}{2}\begin{bmatrix}u \\ v\end{bmatrix}^⊤\!\! ⋅ \begin{bmatrix} & A \\ A^⊤ & \end{bmatrix} ⋅\begin{bmatrix}u \\ v\end{bmatrix} \qquad\text{s.t.}\qquad \begin{aligned} \begin{bmatrix}u \\ v\end{bmatrix}^⊤\!\! ⋅ \begin{bmatrix} & \\ & \end{bmatrix} ⋅\begin{bmatrix}u \\ v\end{bmatrix} &= 1 \\ \begin{bmatrix}u \\ v\end{bmatrix}^⊤\!\! ⋅ \begin{bmatrix} & \\ & \end{bmatrix} ⋅\begin{bmatrix}u \\ v\end{bmatrix} &= 1 \end{aligned} $$
Which can be classified/summarized as QCQP with the properties:
- $Q$ symmetric (but not necessarily positive definite!)
- $P_k$ symmetric positive semi-definite.
- The feasible set is compact, hence a global optimum exists
- Some block/sparsity structure
Additionally, this can be classified as a biconvex problem and bilinear program.
Questions:
- What does standard optimization theory have to say about this problem? General QCQPs are NP-hard, but apparently some classes of QCQP can be relaxed towards SDP or even SOCP problems.
- What are effective, off-the-shelve algorithms for solving such problems? Can we recover methods like the alternating power iteration? Are there modified Newton Methods with quadratic convergence?
References:
- https://web.stanford.edu/class/msande311/lecture15.pdf Constructs a SDP relaxation and claims exactness.
- Multiple works construct unconstrained proxies that are optimized via gradient descent [Hasan 2008], [Feng 2017], [Xu 2019], [Feng 2021]