I would like to solve the following optimization problem for vectors $\mathbf{u} \in \mathbb{R}^m$ and $\mathbf{v} \in \mathbb{R}^n$, given a matrix $\mathbf{h} \in \mathbb{R}_{\geq 0}^{m \times n}$ of non-negative entries:
\begin{align*} \begin{cases} \mathrm{minimize} \ || \mathbf{h} - \mathbf{u}\mathbf{v}^{\mathrm{T}}||_{\mathrm{F}} & \\ \mathrm{subject \ to} \ \left(\mathbf{h} - \mathbf{u}\mathbf{v}^{\mathrm{T}}\right)_{ij} \leq 0 & \forall \ \ i \in \{1, \dots, m\}, \ j \in \{1, \dots, n\} \end{cases} \rm{,} \end{align*}
where $||\mathbf{A}||_{\mathrm{F}} \equiv \mathrm{Tr}\left(\mathbf{A}^{\mathrm{T}} \mathbf{A}\right)$ is the Frobenius norm. That is, I would like a rank-1 matrix $\mathbf{u}\mathbf{v}^{\mathrm{T}}$ that most strictly upper bounds (as measured by the Frobenius norm) $\mathbf{h}$ element-wise.
My question is related to this one, with the added constraint that the rank-1 matrix is upper-bounding. I know the problem is nonconvex, but I am wondering if there is a known convex relaxation of the problem, or, if not, what is known about the problem generally. Thanks!
Given a nonnegative matrix $\mathrm A \in \mathbb R^{m \times n}$, we have the optimization problem in $\mathrm x \in \mathbb R^m$ and $\mathrm y \in \mathbb R^n$
$$\begin{array}{ll} \text{minimize} & \| \mathrm x \mathrm y^{\top} - \mathrm A \|_{\mathrm F}^2\\ \text{subject to} & \mathrm x \mathrm y^{\top} \geq \mathrm A\end{array}$$
where the objective function is
$$\| \mathrm x \mathrm y^{\top} - \mathrm A \|_{\mathrm F}^2 = \mbox{tr} \left( (\mathrm x \mathrm y^{\top} - \mathrm A)^{\top} (\mathrm x \mathrm y^{\top} - \mathrm A) \right) = \cdots = \| \mathrm x \|_2^2 \| \mathrm y \|_2^2 - 2 \mathrm x^{\top} \mathrm A \, \mathrm y + \| \mathrm A \|_{\mathrm F}^2$$
Taking the partial derivatives and finding where they vanish, we obtain
$$(\mathrm x \mathrm y^{\top} - \mathrm A) \, \mathrm y = 0_m \qquad \qquad \qquad \mathrm x^{\top} (\mathrm x \mathrm y^{\top} - \mathrm A) = 0_n^{\top}$$
which can be written in matrix form as follows
$$\begin{bmatrix} \| \mathrm y \|_2^2 \, \mathrm I_m & - \mathrm A\\ -\mathrm A^{\top} & \| \mathrm x \|_2^2 \, \mathrm I_n\end{bmatrix} \begin{bmatrix} \mathrm x\\ \mathrm y\end{bmatrix} = \begin{bmatrix} 0_m\\ 0_n\end{bmatrix}$$
Assuming that $\mathrm x \neq 0_m$ and that $\mathrm y \neq 0_n$, using Gaussian elimination we obtain
$$(\| \mathrm x \|_2^2 \, \| \mathrm y \|_2^2 \, \mathrm I_m - \mathrm A \mathrm A^{\top}) \, \mathrm x = 0_m \qquad \qquad \qquad (\| \mathrm x \|_2^2 \, \| \mathrm y \|_2^2 \, \mathrm I_n - \mathrm A^{\top} \mathrm A) \, \mathrm y = 0_n$$
Thus, we conclude that $\| \mathrm x \|_2 \, \| \mathrm y \|_2$ is a singular value of $\mathrm A$, i.e.,
$$\| \mathrm x \|_2 \, \| \mathrm y \|_2 = \sigma_i (\mathrm A)$$