As defined in this thread  I would like to see a derivation of the closed form soft-thresholding solution for the LASSO using the KKT optimality conditions. Does anybody know how to do it?
22056
For the lasso problem $\min_\beta (Y-X\beta)^T(Y-X\beta)$ such that $\|\beta\|_1 \leq t$. I often see the soft-thresholding result $$ \beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\gamma)^+ $$  for the orthonormal $X$ case. It is claimed that the solution can be "easily shown" to be such, but I've never seen a worked solution. Has anyone seen one or perhaps has done the derivation?
61271
I've to solve the following nonlinear matrix equation, and I was wondering if there is any bigger class where to fit such an equation so that I can either:   Obtain a closed-form solution (ideal) Use appropriate algorithms to solve it numerically.   Assume that $V\in\mathbb{R}^{1\times k}$, $B_i\in\mathbb{R}^{k\times 1}$, $T_i\in\mathbb{R}^{k \times k}$ with $i=1,\dots,k$, and finally $L\in\mathbb{R}^{1\times k}$. The equation reads:  $$V - \sum_{i=1}^{k} VB_iVT_i = L$$  And it has to be solved for $V$ (all the other matrices are assumed to be known). Any help or suggestion will be extremely appreciated! Thanks!!!
50986
This question regards the problem of . Vectors and matrices will be denoted in bold.  Premises. Let $N,K$ be given integers, with $K \gg N &gt; 1$. The transpose of matrix $\mathbf{A}$ will be denoted with $\mathbf{A}^T$. Suppose the following statistical model holds $$ (*) \quad \mathbf{y} = \mathbf{Hx + n}, \quad \mathbf{n} \sim \mathcal{N}_{K}(\mathbf{0}, \mathbf{C})  $$ where $\mathbf{y} \in \mathbb{R}^{K \times 1}$ are the observables, $\mathbf{H} \in \mathbb{R}^{K \times N}$ is a known full-rank matrix, $\mathbf{x} \in \mathbb{R}^{N \times 1}$ is a deterministic vector of unknown parameters (which we want to estimate) and finally $\mathbf{n} \in \mathbb{R}^{K \times 1}$ is a disturbance vector (noise) with a known (positive definite) covariance matrix $\mathbf{C} \in \mathbb{R}^{K \times K}$. The  (ML) estimate of $\mathbf{x}$, denoted with $\hat{\mathbf{x}}_{ML}$, is given by $$ (1) \quad \hat{\mathbf{x}}_{ML} = (\mathbf{H}^T \mathbf{C^{-1}} \mathbf{H})^{-1} \mathbf{H}^T \mathbf{C}^{-1} \mathbf{y} $$ and this is also the standard formula of Generalized Linear Least Squares (GLLS). Consider the standard formula of Ordinary Least Squares (OLS) for a linear model, i.e. $$ (2) \quad \hat{\mathbf{x}}_{OLS} = (\mathbf{H}^T \mathbf{H})^{-1} \mathbf{H}^T \mathbf{y} $$ As a final note on notation, $\mathbf{I}_K$ is the $K \times K$ identity matrix and $\mathbf{O}$ is a matrix of all zeros (with appropriate dimensions). Now, for the problem at hand, assume that $\mathbf{C}^{-1} = \mathbf{I}_K + \mathbf{X}$, where $\mathbf{X} \in \mathbb{R}^{K \times K}$ is a symmetric, invertible matrix (and, for the formalism to make sense, $\mathbf{X}$ is such that $\mathbf{I}_K + \mathbf{X}$ is invertible and the inverse is positive definite). In this case, it can be proven (using matrix inversion lemma) that $$ (3) \quad (\mathbf{H}^T \mathbf{C^{-1}} \mathbf{H})^{-1} \mathbf{H}^T \mathbf{C}^{-1} = (\mathbf{H}^T \mathbf{H})^{-1} \mathbf{H}^T + \mathbf{Q} $$ where the expression for the matrix $\mathbf{Q} \in \mathbb{R}^{N \times K}$ can be found (I will omit it here). Now, finally,  Proposition 1. If $\mathbf{H}^T\mathbf{X} = \mathbf{O}_{N,K}$, then equation $(1)$ degenerates in equation $(2)$, i.e., there exists no difference between GLLS and OLS.  The proof is straigthforward and is valid even if $\mathbf{X}$ is singular. Now, my question is  Question: Can an equation similar to eq. $(3)$ (which "separates" an OLS-term from a second term) be written when $\mathbf{X}$ is a singular matrix?  I am not interested in a closed-form of $\mathbf{Q}$ when $\mathbf{X}$ is singular. But I do am interested in understanding the concept beyond that expression: what is the actual role of $\mathbf{Q}$? In which space does it operate?  I found this problem during a numerical implementation where both OLS and GLLS performed roughly the same (the actual model is $(*)$), and I cannot understand why OLS is not strictly sub-optimal. I found this slightly counter-intuitive, since you know a lot more in GLLS (you know $\mathbf{C}$ and make full use of it, why OLS does not), but this is somehow "useless" if some conditions are met. What are these conditions?  As a final note, I am rather new to the world of Least Squares, since I generally work within a ML-framework (or MMSE in other cases) and never studied the deep aspects of GLLS vs OLS, since, in my case, they are just intermediate steps during the derivation of MLE for a given problem.  If the question is, in your opinion, a bit too broad, or if there is something I am missing, could you please point me in the right direction by giving me references? Preferably well-known books written in standard notation.
74071
I'am trying to derive mathematically the lowest $\lambda$ at which all coefficients are zero, reffering to the Exercise 2.1 of the book .  The result should be $\lambda_{min}=\max_j |X_j^Ty|$. I hope this isnt a duplicate, because it is also discussed . However my math skills are very restricted, so I don't understand the solution. I hope that someone can help me to understand the mathematical details behind the derivation.  The LASSO is defined as:  $\min_\beta \frac{1}{2}||y-X\beta||_2^2 +\lambda||\beta||_1$  My approach was following the KKT-conditions, we get  $X^T (y-X\hat{\beta})=\lambda s$  with $s$ as the subgradient.  $\beta=0$ leads to  $X^Ty=\lambda s \Leftrightarrow \frac{X^Ty}{s}=\lambda$  And here im stucking. How I can get from there to this $\lambda_{min}=\max_j |X_j^Ty| $  EDIT: The Exercise question of the book is: "Show that the smallest value of  such that the regression coefficients estimated by the lasso are all equal to zero is given by"  $\lambda_{max}=|\frac{1}{N}\langle x_j,y\rangle|$  EDIT2: Source of the KKT-Condition
35720
I am reading the Pattern Recognition and Machine Learning book by Bishops. I have some difficulties proving the (6.21) equation. Can someone help me?   N.B: If someone has a better title for this question, i'm opened to it as i couldn't find the good words.
96203
I have come across the term "closed-form solution" quite often. What does a closed-form solution mean? How does one determine if a close-form solution exists for a given problem? Searching online, I found some information, but nothing in the context of developing a statistical or probabilistic model / solution.   I understand regression very well, so if any one can explain the concept with reference to regression or model-fitting, it will be easy to consume. :)
62306
What would the normalising  constant be of the following, or atleast an approximation? I would like to avoid sampling.  $$f(\theta)=\exp(-k_1e^{-k_2\theta^2}-\theta^2)\qquad\theta\in(-\infty,\infty), \quad k_1,k_2&gt;0$$  In the event that its not possible, what would be a valid polynomial lower bound on $\log(f(\theta))$, that would take into account $k_1$  For anyone, who is interested, I end up with this expresssion because I place a Gaussian prior over (a squared exponential) kernel parameters, and trying to use variational bayes (hence, a lower bound).
71439
Given the vectors $x_0, \theta \in \mathbb{R}^n$, $\varepsilon\in \mathbb{R}^+$, and symmetric positive definite matrices $A, \Sigma\in \mathbb{R}^{n\times n}$, how the following optimization problem can be solved (possibly in closed form)? $$\begin{array}{ll} \underset{x \in \mathbb{R}^n}{\text{minimize}} &amp; (x - x_0)^\top A (x - x_0)\\ \text{subject to} &amp; \sqrt{x^\top \Sigma x} + x^\top \theta \leq \varepsilon\end{array}$$ What I tried: First, note that the problem is convex since both the objective is convex in $x$, and the constraint defines a convex set in $x$. Write the Lagrangian of the problem as $$L(x,\lambda) = (x-x_0)^\top A (x-x_0) + \lambda (\sqrt{x^\top \Sigma x} + x^\top \theta  - \varepsilon). $$ The KKT conditions for this problem leads to the system: $$ \begin{cases} A (x-x_0) + \lambda \left(\frac{\Sigma x}{\sqrt{x^\top\Sigma x}}+ \theta \right) = 0 \\ \lambda\left(\sqrt{x^\top \Sigma x} + x^\top \theta  - \varepsilon \right) = 0 \\ \sqrt{x^\top \Sigma x} + x^\top \theta  - \varepsilon \leq 0\\\lambda\geq 0 \end{cases} $$ However, the solution of this system gets complicated in my calculation and I am not able to find a closed-form solution. Any suggestion?
78069
I'm trying to understand the derivation of the equations for the logistic regression. I'm following the cs229 notes:    At some point in the derivation, in the notes we need to maximize the log-likelihood of the parameters:  ℓ(θ) = log L(θ) = y log h(x) + (1 - y) log(1-h(x))  In the notes, after the derivation we get:  $\frac{\partial}{\partial \theta_j}$ = (y $\frac 1 {h(x)}$ - (1 - y) $\frac 1 {1 - h(x)}$) $\frac{\partial}{\partial \theta_j}$h(x)  Shouldn't this be:  $\frac{\partial}{\partial \theta_j}$ = (y $\frac 1 {h(x)}$ + (1 - y) $\frac 1 {1 - h(x)}$) $\frac{\partial}{\partial \theta_j}$h(x)  I've been looking at this for a while and I can't see where this minus sign is coming from...  Thanks for your help!
114421
The question  demonstrates solution paths for the lasso estimator that are not monotonic. That is, some of the cofficients grow in absolute value before they shrink.  I've applied these models to several different kinds of data sets and never seen this behavior "in the wild," and until today had assumed that they were always monotonic.  Is there a clear set of conditions under which the solution paths are guaranteed to be monotone? Does it affect the interpretation of the results if the paths change direction?
92467
My problem is we want to minimize $1/2 \cdot \text{Norm}(w)^2$ under suitable constraints $y(i){[w^Tx_i+b]-1}$.  We write the Lagrangian and get the above equations.  I have a problem in differentiating with respect to $w$ can somebody elaborate on that? How do we get first equation?
61472
I`m using the Newton-Raphson method for obtaining MLE for parameters for maximizing my objective function. At each iteration, I want to check that is the Hessian matrix negative definite or not and I see the Hessian matrix is not negative definite at some iterations. So, I want to use the Fisher scoring algorithm ( of derivation) In this situation, the Fisher information matrix is indefinite!! Is it possible? What are the reasons for this? Are the second-order derivatives wrong? Or are values of expectations incorrect?
100123
Consider a linear system of equations $Ax = b$.   If the system is overdetermined, the least squares (approximate) solution minimizes $||b - Ax||^2$. Some source sources also mention $||b - Ax||$. If the system is underdetermined one can calculate the minimum norm solution. But it does also minimize  $||b - Ax||$, or am I wrong?   But if least squares is also a minimum norm, what is the difference, or the rationale of the different naming?
57723
Conceptually, I don't understand what least angle regression Least Angle Regression (LARS) is and why it solves LASSO ().  We know that LASSO is:   $$\arg \min_x {\left\| A x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1}$$  From my understanding LARS is exactly like line search from CGD, where you take the variable that gives you the most desire result and iterate through.  Can someone give a walk through on how LARS solves LASSO?
33015
I have been reading many articles on LASSO regression, and everyone claims that LASSO address multicollinearity showing contour plots of cost function touching the corner of the diamond(x1+x2). In the first place, I didn't understand how does this phenomenon translate to addressing multicollinearity when there are many groups of correlated variables in the data.  Verbatim from one of the research paper: "• If there are grouped variables (highly correlated between each other) LASSO tends to select one variable from each group ignoring the others".
93955
How do ridge, LASSO and elasticnet regularization methods compare? What are their respective advantages and disadvantages? Any good technical paper, or lecture notes would be appreciated as well.
52575
I'm trying to make sense of a derivation I'm following from the lecture notes of Stanford's ML course.  Specifically the notes are here:   I'm particular I'm interested in the step where they are optimizing the lower bound of the log-likelihood by finding the derivative of that function w.r.t the mean (top of page 7). I'm a bit stuck on going from line 1 to line 2 in that sequence.  To copy here (using abbreviated notation for space):  $$ \nabla \mu_s \sum_{i=1}^{m}\sum_{j=1}^{k} w_j^{(i)}\log\frac{\alpha_j \exp\psi_{j}^{(i)}\phi_j}{w_j^{(i)}}  \qquad(1) $$ $$ \nabla \mu_s \sum_{i=1}^{m}\sum_{j=1}^{k} w_j^{(i)}\psi_{j}^{(i)}\qquad(2) $$ where $\psi_{j}^{(i)} =-\frac{1}{2}(x^{(i)}-\mu_j)^T\Sigma^{-1}_{j}(x^{(i)}-\mu_j)$ and $\alpha_j=\frac{1}{(2\pi)^{n/2}|\Sigma_j|^{1/2}}$.  The quantity $\mu_s$ is the mean (of a multivariate gaussian distribution) for class $s$.    In short, I'm not sure how they get from (1) to (2).  From just changing the log of (1) I see:  $$ \nabla \mu_s \sum_{i=1}^{m}\sum_{j=1}^{k} w_j^{(i)}\log \left(\alpha_j \exp\psi_{j}^{(i)}\phi_j\right) - w_j^{(i)}\log w_j^{(i)} \qquad(1) $$  To get to their form (2) my impression is that they take pre-emptively discard terms that would contain derivatives of $w_j^{(i)}$ (w.r.t. $\mu_s$).  At least if you assume that much, you get to (2).  However, as they show earlier in that PDF,  $$ w_j^{(i)} = p(z^{(i)}=j | x^{(i)}) =\frac{p(x^{(i)}|z^{(i)}=j)p(z^{(i)}=j) }{\sum_j p(x^{(i)},z^{(i)}=j) } $$ i.e. this quantity is the posterior distribution of the class labels.  Intuitively, it seems like $\partial w_j^{(i)}/ \partial \mu_s$ should be non-zero.  After all, changing the location of the mean $\mu_s$ would change your posterior probability for a particular class given the same data.  (Right?).  Just from a mechanical point of view, $\partial w_j^{(i)}/\partial \mu_j$ would seemingly have some non-zero terms since $p(x^{(i)}|z^{(i)}=j) \sim \mathcal{N}(\mu_j, \Sigma_j)$.  If I work through the algebra, I get  $$ \frac{\partial w_j^{(i)}}{\partial \mu_j} = w_j^{(i)}(1-w_j^{(i)})\frac{\partial \psi^{(i)}_{j}}{\partial \mu_j} $$  What am I missing here?  If I take the log-likelihood (without even thinking about EM algorithm),    $$ \ell = \sum_{i=1}^{m}\log \sum_{j=1}^{k}p(x^{(i)}|z^{(i)}=j)p(z^{(i)}=j) $$ and differentiate w.r.t $\mu_s$, I correctly get  $$ \mu_s^* = \frac{\sum_{i=1}^{m}w_s^{(i)}x^{(i)}}{\sum_{i=1}^{m}w_s^{(i)}} $$  so I'm comfortable with the eventual result, just not the intermediate steps.