# On optimizing a function whose projection and projected vector go through a linear transformation

Assume the two sets of vectors $\{\mathbf{a}_1,\ldots,\mathbf{a}_N\}$ and $\{\mathbf{b}_1,\ldots,\mathbf{b}_N\}$ of equal length. My goal is to find the optimum matrix $\mathbf{C}$ to the following optimization problem: \begin{align} \max_{\mathbf{C}} \min_{i} \left|\operatorname{proj}_{\mathbf{C}\mathbf{a}_i}^\perp\mathbf{C}\mathbf{b}_i\right|^2. \end{align} Here, $\operatorname{proj}_{\mathbf{C}\mathbf{a}_i}^\perp$ is the projection operator on the subspace orthogonal to that spanned by $\mathbf{C}\mathbf{a}_i$, $\mathbf{C}$ is of fixed size, and some constraint on $\mathbf{C}$ must be imposed to avoid solutions that tend to infinite.

Even if a solution is not provided, partial solutions, approximations or reformulations of this problem are welcomed!

Here is a classic solution based on the semidefinite relaxation of a rank constraint. To begin, let us write $C\in\mathbb{R}^{r\times n}$. Let $x_{i}=Ca_{i}$ and $y_{i}=Cb_{i}$. Then the maxi-min is equivalently posed $$\text{maximize }t\text{ subject to }y_{i}^{T}y_{i}-\frac{y_{i}^{T}x_{i}x_{i}^{T}y_{i}}{x_{i}^{T}x_{i}}\ge t\text{ for all }i$$ Suppose we introduce the semidefinite matrix decision variable $Z=C^{T}C\succeq0$ and imposed that $\mathrm{rank}(Z)\le r$. Then a valid, although possibly nonunique choice of $C$ can always be recovered from $Z$ using the Cholesky factorization.

Now, the following is obvious from the cyclic property of trace \begin{align} \alpha_{i} & =y_{i}^{T}y_{i}=\mathrm{Tr}\, Zb_{i}b_{i}^{T}\\ \beta_{i} & =x_{i}^{T}y_{i}=\frac{1}{2}\mathrm{Tr}\, Z(a_{i}b_{i}^{T}+b_{i}a_{i}^{T})\\ \gamma_{i} & =x_{i}^{T}x_{i}=\mathrm{Tr}\, Za_{i}a_{i}^{T} \end{align}

all of which are linear constraints with respect to $Z$. Finally, the following is obvious from the Schur complement lemma

$$y_{i}^{T}y_{i}-\frac{y_{i}^{T}x_{i}x_{i}^{T}y_{i}}{x_{i}^{T}x_{i}}\ge t\iff\begin{bmatrix}\alpha_{i}-t & \beta_{i}\\ \beta_{i} & \gamma_{i} \end{bmatrix}\succeq0.$$

Combined, the nonconvex problem is $$\text{maximize }t\text{ subject to constraints for all }i,\,Z\succeq0,\,\mathrm{rank}(Z)\le r.$$ Dropping the rank constraint yields the classic semidefinite relaxation, which is a convex problem you can readily solve using e.g. cvx or YALMIP.

If the relaxed solution satisfies $\mathrm{rank}(Z)\le r$, then we are done, and a solution for $C$ is recovered by taking the Cholesky factorization. If $\mathrm{rank}(Z)>r$ then there are a bunch of standard techniques to force the solution rank to go down. For example, we can modify the objective by $t-\eta\mathrm{Tr}\, Z$, where $\eta>0$ is a small constant introduced to promote low-rank solutions via the trace penalty.

• Thank you Richard. I had explored the rank relaxation, but I had reached a different problem that was not convex. Commented Mar 11, 2016 at 8:56
• Do you mean that my proposed rank relaxation is nonconvex, or that the problem as stated in the original prompt is incomplete, and that missing aspect is nonconvex? Commented Mar 11, 2016 at 15:47
• Oh no. I meant that your solution is good and that the solution I got to was bad. One thing though: Without any extra constraint, Z would tend to infinite. Also, I think in this framework, the extra term tr(Z) does not induce low rankness. Commented Mar 11, 2016 at 16:00
• Yes, you're right. The constraints (with and without the rank statement) are homogeneous with respect to $Z$, in that if $Z$ is a feasible point, then $\alpha Z$ is also feasible for any $\alpha\ge0$. For problems of this form, restricting tr(Z)=1 would often induce sparsity. Commented Mar 11, 2016 at 17:38