4
$\begingroup$

I'm currently trying to minimize the following function: $$\min_{\mathbf x,\mathbf y,s} \|F\mathbf x-\mathbf a\|_2^2 + \|SF\mathbf y-\mathbf b\|_2^2 + \lambda \|\max(\mathbf x, \mathbf y)\|_1,$$ $$\mathbf x>\mathbf 0, \mathbf y>\mathbf 0.$$ Here $F$ and $S$ are both linear operators. $F$ is a discrete Fourier transform, $S$ is "shift by $s$ in Fourier domain" operator: $(Sf)_k = f_k \cdot e^{-2\pi i u_k s}$, and $\max(\mathbf x, \mathbf y)$ is elementwise.

So the problem is basically regularized least squares, and should hopefully lead to sparse solutions $\mathbf x, \mathbf y$ having nonzero elements in about the same locations (up to explicit shift $s$).

Note that it is almost linear but for the discontinuity in regularizer and nonlinear dependency on $s$. For fixed $s$ I get good results ($\mathbf x,\mathbf y$ close to true values) using LBFGS method. When optimizing separately for each $s$ from a range, I see a clear minimum around the true value. But when I include the $s$ variable into optimization, its value basically doesn't change from the initial one, no matter if it is close or far from the truth.

I guess the problem is that the function (of $s$) has many local minima all over the range. How to approach the problem correctly, or where to read about similar ones? I had no success with other common optimization algorithms from scipy I tried.

$\endgroup$
  • $\begingroup$ Can you just do an inner/outer optimization? $\displaystyle \min_{x,s} ~f(x,s) = \min_s~ g(s)$ where $\displaystyle g(s) = \min_x~ f(x,s)$. The inner problem you can solve with quasi-newton. The outer problem is 1-dimensional so you can solve it with a secant method or something like that. $\endgroup$ – Nick Alger Feb 11 '18 at 23:46
  • $\begingroup$ The regularizer is easily fixed by introducing slack variables $\mathbf z$ and replacing $\|\max(\mathbf x,\mathbf y)\|$ by $\|\mathbf z\|$, if you add constraints $\mathbf z\ge \mathbf x$ and $\mathbf z\ge \mathbf y$. If you further add another set of slack variables, you can convert the $l_1$ norm into a linear sum. $\endgroup$ – Wolfgang Bangerth Feb 13 '18 at 3:52
3
$\begingroup$

Here is one possibility to try out:

I think you could decompose this problem into a convex and non-convex one by alternation. One could maybe first optimize for $\mathbf x$ and $\mathbf y$: $$\min_{\mathbf x,\mathbf y} \|F\mathbf x-\mathbf a\|_2^2 + \lambda \|\max(\mathbf x, \mathbf y)\|_1,$$ keeping $\mathbf S$ constant.

In the next stage, we could solve for $\mathbf S$: $$\min_{s} \|SF\mathbf y-\mathbf b\|_2^2$$ this time keeping all the rest fixed. Maybe it is easier to solve this second equation via direct methods.

Starting from certain initialization, we could alternate both solutions until we arrive at the desired one. Other splits are also possible and might work better, such as first solving for $\mathbf x$, etc.

$\endgroup$
  • $\begingroup$ Thanks for the suggestion, will try it! And did you mean optimizing the whole function for x and y first - all three terms, not two of them as you wrote? $\endgroup$ – aplavin Feb 11 '18 at 15:41
  • $\begingroup$ well without S, you only have two right? $\endgroup$ – Tolga Birdal Feb 11 '18 at 19:38
  • $\begingroup$ ‖SFy−b‖ also dependes on y. $\endgroup$ – aplavin Feb 12 '18 at 4:21
  • $\begingroup$ In the second yes. But as I wrote, it might be kept fixed. I chose this one because you mentioned that you could obtain a good solution for the first part, once S is known. $\endgroup$ – Tolga Birdal Feb 12 '18 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.