3
$\begingroup$

Say the model is $F(x_1)G(x_2)Z(x_3) = y \in \mathbb{R}^N$, with $F,G,Z$ explicitly known, we are given observation of $y$ as $y_b \in \mathbb{R}^N$ to find the value of $x_1$, $x_2$, $x_3$ for each sample. Clearly this is an underdetermined inverse problem.

I have seen some iterative algorithm like this,

  1. start with random number of $x_1$, $x_2, x_3$.
  2. choose $x_1$, keep $x_2$, $x_3$ constant as change $x_1$ to $x_1^*$ such that

$$F(x_1^*)G(x_2)Z(x_3) = y_b$$

  1. update $x_1 = x_1^*$

  2. same thing for $x_2$, but fix $x_1$, $x_3$, and update $x_2 = x_2^*$.

  3. repeat for $x_3$, and do the whole process several iterations until it doesn't change

  4. final result is taken as the solution to the inverse problem.

I have seen this philosophy many times across different areas of computer science, just hope to know what is the big picture behind it. like ADMM?

$\endgroup$

1 Answer 1

5
$\begingroup$

A general name for this approach is "Block Coordinate Descent." It's important to understand that convergence isn't guaranteed without additional hypotheses.

ADMM is not simply block coordinate descent- it's a more complicated method that is optimizing with respect to primal variables $x$ and $z$ in each iteration and then adjusting the Lagrange multiplier and penalty parameter.

$\endgroup$
1
  • $\begingroup$ just found in a 1977 paper, it is called nonlinear Gauss Seidel method. oh yeah, now it looks more familiar. $\endgroup$ Aug 23, 2019 at 3:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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