Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a given $N\times P$ matrix $X$ (full rank with columns ${\bf x}_p$, $p=1,\ldots,P$), a given vector ${\bf y}\in R^N$ and a thresholding function $\eta_\lambda(|x|)=(|x|-\lambda)_+$ with $\lambda>0$.

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 $$ \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. $$ Repeat with a cycling rule, successively letting $p=1,2,\ldots, P, 1,2 \ldots$

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.

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)?

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.