most recent 30 from http://mathoverflow.net 2013-05-19T07:46:01Z http://mathoverflow.net/feeds/question/23556 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/23556/convergence-to-a-unique-fixed-point Sardy 2010-05-05T08:04:46Z 2010-05-05T08:04:46Z

<p>Consider a given $N\times P$ matrix $X$ (full rank with columns <code>${\bf x}_p$</code>, $p=1,\ldots,P$), a given vector ${\bf y}\in R^N$ and a thresholding function $\eta_\lambda(|x|)=(|x|-\lambda)_+$ with $\lambda>0$.</p> <p>Start with a vector ${\boldsymbol \alpha \in R^P}$, define ${\bf r}_{-p}({\boldsymbol \alpha})={\bf y}-X {\boldsymbol \alpha}+ \alpha_p {\bf x}_p$, and define a sequence of vectors that changes only one entries to the current iterate, say the $p$th one, to <code>$$ \alpha_p^{\rm new} =\frac{{\bf r}_{-p}({\boldsymbol \alpha}^{\rm old})^{\rm T} {\bf x}_p}{ \|{\bf x}_p \|_2^2 } \left \{\frac{\eta_{\lambda}(|{\bf r}_{-p}({\boldsymbol \alpha}^{\rm old})^{\rm T} {\bf x}_p|)}{ |{\bf r}_{-p}({\boldsymbol \alpha}^{\rm old})^{\rm T} {\bf x}_p|}\right \}^\gamma. $$</code> Repeat with a cycling rule, successively letting $p=1,2,\ldots, P, 1,2 \ldots$</p> <p>Note that the case $\gamma=0$ amounts to solving the least squares problem $$ \min_{\boldsymbol \alpha \in R^P} \| {\bf y}- X {\boldsymbol \alpha}\|_2^2, $$ by a coordinate descent algorithm; also the case $\gamma=1$ amounts to solving the $\ell_1$-penalized least squares problem $$ \min_{\boldsymbol \alpha \in R^P} \frac{1}{2}\| {\bf y}- X {\boldsymbol \alpha}\|_2^2 + \lambda \| {\boldsymbol \alpha}\|_1, $$ by a coordinate descent algorithm. Fact: both algorithms converge to a unique point: the minimum of its corresponding optimization problem.</p> <p>Questions: (1) For a given starting vector ${\boldsymbol \alpha}$, does the sequence converge to a fixed point for all $\gamma$'s? (2) If so, is the fixed point unique (regardless of the starting vector)?</p>