0

In the article ''' Chartrand, Rick, and Wotao Yin. "Iteratively reweighted algorithms for compressive sensing." Acoustics, speech and signal processing, 2008. ICASSP 2008. IEEE international conference on. IEEE, 2008. '''

It is given that one iteration of iterative reweighed least squares problem can be written as $\min \sum_{i=1}^N w_i u_i^2 $ subject to $\Phi u = b $ which has a closed form solution given as

$u^{(n)} = Q_n \Phi^T (\Phi Q_n \Phi^T)^{-1} b$. where $Q_n$ is the diagonal matrix containing entries $1/w_i$ And the closed form equation can be derived from the Euler Lagrange equation. Can someone please help me to get the derivation of the iteration

seeker
  • 17
  • 2
    Lagrange multipliers... Better asked at math.se. – Dirk Feb 20 '18 at 05:18
  • I understood till $\min_u u^T W u + \lambda ||\Phi u - b ||_2^2$. which can be written as ($ \grad =0$) W u + \lambda (\Phi^T \Phi u - \Phi^T b) =0 – seeker Feb 20 '18 at 05:26

1 Answers1

0

What you did in your comment was to penalize the constraint. That's something different.

Here you form the Lagrangian $$ L(u,\lambda) = \tfrac12u^TQ_n^{-1} u + \lambda^T(\Phi u-b) $$ with a (vector) Lagrange multiplicator $\lambda$ (the factor $\tfrac12$ is for convenience and does only scale $\lambda$). Now a pair $(u,\lambda)$ is optimal if $$ \partial_u L(u,\lambda) = Q_n^{-1}u + \Phi^T\lambda = 0 $$ $$ \partial_\lambda L(u,\lambda) = \Phi u-b = 0. $$ Multiply the first equality by $\Phi Q_n$ to get $$ \Phi u = -\Phi Q_n\Phi^T\lambda $$ and by the second equality you get $$ \lambda = -(\Phi Q_n\Phi^T)^{-1}b. $$ With this, go back to the first equality to get $$ Q_n^{-1} u -\Phi^T(\Phi Q_n \Phi^T)^{-1}b $$ which is (basically) what you want.

Dirk
  • 11,680