# Element-wise upper bound by rank-1 matrix

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!

• I suspect that alternating least squares be the "workhorse" algorithm to solve this problem. Do you know this method? – Alex Silva Nov 3 '16 at 12:51
• @Alex Yes, this was alluded to in the question I linked, though it is mentioned there that ALS may not give an optimal solution (which is probably unavoidable since the problem is nonconvex). Following this paper, I suppose the projection operation onto the constrained subspace is that which nullfies all the elements of the residual which violate the bound (thus saturating the bound there). It is interesting that the first step in the algorithm resembles the solution to the unconstrained problem. I'll try this; thank you for your suggestion. – Adrian Nov 3 '16 at 15:43

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)$$

• From the question I linked, if x and y are the left and right singular vectors of A, respectively, corresponding to the same singular value and normalized to its square root, then the two last equations you wrote will be satisfied. In this case, the squared Frobenius norm will be the sum of the squares of the remaining singular values of A, and this will be minimized when x and y are the principal singular vectors (there is more than one local minimum). However, I am asking what is known about the solution to the constrained problem, which seems substantially harder. – Adrian Nov 2 '16 at 23:47