Vtgyjfy

I have an $n$-dimensional complex vector space, and I want to minimize the $L_infty$ norm of a point that is constrained to an $m$-dimensional affine subspace. That is,

Given $mathbf{z} in mathbb{C}^n$ and $mathbf{M}inmathbb{C}^{ntimes m}$, find $underset{mathbf xinmathbb{C}^m}{argmin} |mathbf{z}+mathbf{M}mathbf{x}|_infty$.

The columns of $mathbf{M}$ are orthonormal with $mathbf{M}^*mathbf{M}=mathbf{I}$, and $mathbf{M}^*mathbf{z} = mathbf{0}$. In my application, the columns of $mathbf{M}$ are taken from an $ntimes n$ Fourier matrix in such a way that $mathbf{M}mathbf{M}^*$ is real symmetric.

One approach is to require $left|(mathbf{z}+mathbf{M}mathbf{x})_iright| le lambda$ and minimize the upper bound $lambda$. In the case where all of the variables are real, this gives a linear program. In the problem as posed, we can square both sides and rename the upper bound variable to get $min{Lambda} text{ s.t. }forall i, left|(mathbf{z}+mathbf{M}mathbf{x})_iright|^2 le lambda^2 triangleq Lambda$, which corresponds to a quadratically-constrained linear program. Taking the Lagrange dual leads (if I am not mistaken) to

$max_u inf_{Lambda,mathbf{x}} left( Lambda + sum_{j=1}^n u_j (left|(mathbf{z} + mathbf{M} mathbf{x})_jright|^2 - Lambda) right)$ s.t. $u_i ge 0$,

which evaluates to

$max_u sum_{j=1}^n u_j left|(mathbf{z} - mathbf{M} mathbf{M}^* mathbf{U}^+ mathbf{M} mathbf{M}^* mathbf{U} mathbf{z})_jright|^2$ s.t. $u_i ge 0, sum_{i=1}^n u_i = 1$, where $U_{ij}=delta_{ij} u_i$.

The pseudo-inverse came from solving the expression $-mathbf{M}^* mathbf{U} mathbf{z} = mathbf{M}^* mathbf{U} mathbf{M} mathbf{x}$ (which arises while infimizing the Lagrange dual function). I think the idea is that $n-m$ of the $u_i$ will be zero, so that the expression becomes feasible. That makes sense from a complementary slackness perspective.

I've tried plowing through the remaining maximization. However, I didn't gain any insight, and I don't see how to deal with the non-differentiability of the pseudo-inverse around $u_i=0$. Is this the point where I should just throw gradient ascent at the dual problem and hope for the best? Or is there a better way? Thanks for any pointers.

Thanks for showing interest; too bad nobody has a nice answer! My stop-gap solution was to do gradient descent on the smooth function $sum_i |(mathbf{z}+mathbf{Mx})_i|^p$ for $p=20$. The runtime of this method is not what I would prefer, but it works.

I spoke briefly with Prof. Demanet at MIT, and got a pointer towards proximal iteration techniques for non-smooth optimization. I haven't figured out how to compute the proximal mapping of the constrained complex $L_infty$ norm, though the unconstrained version (e.g. the solution is zero) has a very elegant mapping.

Another possible solution is second-order cone programming, as suggested in example 2.2.b. of F. Alizadeh, D. Goldfarb, "Cone Programming". I am hoping to learn how well this works when the library finishes compiling.

[Edit -- did not spot the comment by dineshdileep until just now. Thank you!]