I'm solving the constrained least squares problem $\underset{u \in [0,1]^N} \min \lVert Au-f \rVert_2^2$ with $u \in \mathbb{R}^N$, $A \in \mathbb{R}^{N \times N}$ and $f \in \mathbb{R}^N$ by using the following modified Jacobi-Method:

$u^{k+1}=\max \{ \min \{ D^{-1} (f - R u^k), 1 \},0 \}$ where $A=D+R$, $D$ is the diagonal of $A$. The $\max$ and $\min$ are applied element-wise, so what I'm doing is basically the standard Jacobi-Method but with projection to the constraint after each iteration.

I need to find out under which conditions on $A$ and $f$ this actually converges to the correct solution of the above problem. Any hints on related literature would be appreciated!

  • $\begingroup$ Is $A$ diagonally dominant, or are their some conditions that would make the spectral radius of $D^{-1}R$ be less than one? $\endgroup$ – copper.hat Feb 25 '13 at 20:15
  • $\begingroup$ yes, A is strictly diagonally dominant. it satisfies all conditions for the normal jacobi method to converge $\endgroup$ – TestTestGuest Feb 25 '13 at 21:29

Here is a (tedious) example that shows that the proposed method will not stop at a solution.

Let $A= \frac{1}{10}\begin{bmatrix} 20 & 10 \\ 10 & 21 \end{bmatrix}$, $f = \frac{1}{160}\begin{bmatrix} 505 \\ 278 \end{bmatrix}$ and $\hat{u} = \frac{1}{2} \begin{bmatrix} 2 \\ 1 \end{bmatrix}$.

Let $\phi(u) = \frac{1}{2} \|Au -f\|_2^2$, and note that $\phi$ is convex and $\nabla \phi(u) = A^T(Au -f)$, and $\nabla( \hat{u}) = \begin{bmatrix} -1 \\ 0 \end{bmatrix}$. Furthermore, note that $\langle \nabla \phi(u), u - \hat{u} \rangle \geq 0 $ or all $u \in [0,1]^2$, hence $\hat{u}$ is the solution to the constrained least squares problem.

We have $D= \frac{1}{10}\begin{bmatrix} 20 & 0 \\ 0 & 21 \end{bmatrix}$, $R = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$. The Jacobi update would give $u_+ = D^{-1}(f-R \hat{u})) = \frac{1}{1344}\begin{bmatrix} 1785 \\ 472 \end{bmatrix}$, which when projected onto $[0,1]^2$ would give $\frac{1}{1344}\begin{bmatrix} 1344 \\ 472 \end{bmatrix} \neq \hat{u}$.

The problem is that the update directions do not align at the solution of the original problem.

  • $\begingroup$ thanks for the tedious example. but i was looking for some result which states that for some specific conditions on $A$ and $f$ this method converges. $\endgroup$ – TestTestGuest Feb 27 '13 at 18:30
  • $\begingroup$ Well, if you have an example that doesn't work and understand why, this may lead to you finding $A,f$ that might work. You are asking for a detailed analysis/result to solve a well-understood problem using a hacked-up method. $\endgroup$ – copper.hat Feb 27 '13 at 22:43

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.