# Tag Info

## Hot answers tagged convex-optimization

6

Let's solve a more general problem (Least Squares with Linear Equality Constraints): \begin{alignat*}{3} \arg \min_{x} & \quad & \frac{1}{2} \left\| A x - b \right\|_{2}^{2} \\ \text{subject to} & \quad & C x = d \end{alignat*} The Lagrangian is given by: $$L \left( x, \nu \right) = \frac{1}{2} \left\| A x - b \right\|_{2}^{2} + {\... 6 Your formulation:$$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{1} $$Has 2 elements: The Fidelity Term This is basically measurements term with the model of AWGN with IID noise. The Regularization Term This is a sparse promoting model by using the Laplace ... 5 There are few options: Stephen Boyd, Lieven Vandenberghe - Convex Optimization. This is the classic in this field. Very well written book. Also have a look on other papers of Boyd on similar subjects such as the The Alternating Direction Method of Multipliers (ADMM). They also have a great MOOC Course Stanford Online CVX 101 - Convex Optimization. Amir Beck ... 5 The problem is given by:$$$$\arg \min_{X} \frac{1}{2} \sum_{k} {\left\| {T}_{k} {X}_{:, k} - {Y}_{:, k} \right\|}_{2}^{2} + \lambda {\left\| G X \right\|}_{2, 1} \\ = \arg \min_{X} \frac{1}{2} \sum_{k} {\left\| {T}_{k} {X}_{:, k} - {Y}_{:, k} \right\|}_{2}^{2} + \lambda \sum_{l} {\left\| G {X}_{:, l} \right\|}_{2}$$$$In the ... 5 The soft-thresholding function finds the minimizer of an objective function that involves data fitting in an \ell_2 sense as well as minimization of the \ell_1 norm (i.e. absolute value). The Lecture Notes - Penalty and Shrinkage Functions for Sparse Signal Processing gives a good discussion of how the soft threshold function is derived. 5 If you want to solve for single value of  \lambda  in the model:$$ \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} $$Then you can use Coordinate Descent method which is the fastest and simplest and doesn't require any matrix inversion. I have a MATLAB code for in my  {L}_{1}  Regularized Least Squares ... 5 Since  \epsilon  is a parameter you need to set why not trade it with another parameter you need to set to create an easily solvable problem (Relaxation of the Problem)? You can transform the problem into the following form ( {L}_{1}  Regularized Least Squares):$$ \arg \min_{x} \frac{1}{2} \left\| A x - z \right\|^{2} + \lambda \left\| x \right\|_{1} $... 5 The solution from the blog you linked goes as following (Coordinating Variable Signs by Paul Rubin, Web Archive): Someone asked me today (or yesterday, depending on whose time zone you go by) how to force a group of variables in an optimization model to take the same sign (all nonpositive or all nonnegative). Assuming that all the variables are ... 5 It is pretty simple to create those Matrices. The real issue with them is their size which is enormous for real world images. For small kernels they are sparse which saves the day. Indeed for the Derivative Operator, which has only 2 elements, they are highly sparse. I built them in MATLAB using: mI = im2double(imread(imageFileName)); mI = mI(11:410, 201:... 5 Their intention is to solve: $$\arg \min_{ J \left( x, y \right) } \sum_{x, y} \left\| J \left( x, y \right) - 255 \right\|_{2}^{2} + \lambda \sum_{x, y} \left\| \nabla J \left( x, y \right) - \nabla I \left( x, y \right) \right\|_{2}^{2}$$ Where$ I \left( x, y \right) $is the input image and$ J \left( x, y \right) $is the output image. They state ... 5 It can easily solved by the Gradient Descent Framework with one adjustment in order to take care of the$ {L}_{1} $norm term. Since the$ {L}_{1} $norm isn't smooth you need to use the concept of Sub Gradient / Sub Derivative. When you integrate Sub Gradient instead of Gradient into the Gradient Descent Method it becomes the Sub Gradient Method. In the ... 5 The Frobenius Norm has multiple equivalent definitions – the useful for error measure is probably this one: $$\left\|M\right\|_\mathrm F = \sqrt{\sum_{p\in M}\left\lvert p\right\rvert^2}$$ That's a root square over all pixels. Root mean squares are very useful cost functions, as they describe the power of a signal. 4 I will solve this for 1D but it could easily generalize into 2D. The nice thing about the TV Norm that it can be re formulated by the$ {L}_{1} $norm of the Derivative Operator: $$\operatorname{TV} \left( x \right) = \sum_{i = 1}^{N - 1} \left| {x}_{i + 1} - {x}_{i} \right| = {\left\| D x \right\|}_{1}$$ Where$ D $is the matrix form of the Derivative ... 4 Indeed the model for the Proximal Gradient Method (Also see Proximal Gradient Methods for Learning) is in the form of: $$F \left( x \right) = f \left( x \right) + g \left( x \right)$$ Where usually$ f \left( x \right) $is convex smooth function and$ g \left( x \right) $is convex non smooth function. Yet the model is quite flexible and you may define ... 4 I will try explaining why would someone use such an option as defining the solution as positive. The Proximal Gradient Method which is the hurt of the FISTA algorithm is basically a generalization of Projected (Sub) Gradient Descent Method. As such, if one knows that the solution lies in a Convex Set and one knows the projection onto that set one could ... 4 I'd say there 3 approaches to do so: Properties of the LMS Filter There is an optimal step size given you know the spectrum of the correlation matrix. You may have a look at Wikipedia's Least Mean Squares Filter at Convergence and Stability in the Mean. Some other approaches related to this might be those from Variable Step Size LMS. You may have a look at ... 4 A MATLAB code which implements the problem as defined and solve it using CVX is given by: %% General Parameters close('all'); clear('all'); %% Simulation Parameters numRows = 6; numCols = 10; varianceFctr = 3; paramLambda = 2.75; %% Generate Data mA = randn(numRows, numCols); vX0 = rand(numCols, 1) >= 0.65; vC = varianceFctr * rand(numRows, 1);... 3 Our goal is to obtain proximal operator of the following function $$g \left( x \right) = {\left\| x \right\|}_{1} + \operatorname{TV}(x).$$ The involved optimization problem for any$z \in \mathbb{R}^dis the following $$\text{argmin}_{x}\left\{g(x) + \frac{1}{2}\|x-z\|^2_2\right\}$$ Denote the following $$g_1(x) := {\left\| x \right\|}_{1} + \frac{1}... 3 Indeed you can not solve the problem ignoring the equality constraints and then project the solution onto the set of solution for the constraint. It is easy to build real world example which shows that. Yet, it might be that in most cases it will work reasonably well. You didn't mention how you solve the LASSO Problem but one of the easiest ways to solve ... 3 There are 2 forms of the Basis Pursuit problem:$$\begin{align*} \text{The \lambda $Form:} & \quad && \arg \min_{x} &&\frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} \\ \text{The$ \epsilon$Form:} && \quad & \arg \min_{x} && {\left\| x \right\|}_{1} \\ && \quad & \text{... 3 Well, in your example, the channel isn't exactly sparse. It has been shown that$\ell_0$minimization can recover any$K$-sparse vector$x$from observations$\Phi x$as long as$2K < {\rm spark}(\Phi) \leq M+1$, when$\Phi$is$M \times N$(so that$x$is$N\times 1$), i.e.,$K<M/2$more or less. This is a necessary condition which means that if$K$... 3 SQP is a method for solving smooth (objective and constraint functions are at least twice differentiable) constrained nonlinear optimization problems. It solves a series of quadratic programming problems to converge to a solution to the Karush-Kuhn-Tucker conditions for the constrained optimization problem. IRLS is a method for solving unconstrained ... 3 The quadratic surface is determined by the autocorrelation matrix of the data, which is always positive definite or positive semi-definite. This means that any stationary point is always a minimum. In the worst case, this minimum is not unique if the matrix is singular, but it can never be a saddle point. 3 Let me rewrite the problem as following: $$\arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \frac{\lambda}{2} {\left\| L x \right\|}_{2}^{2}$$ In order to say something intelligent about the optimal value of$ \lambda one must set an optimization criteria. Since you don't have one there is no well defined answer. What might assist you is ... 3 There are 2 forms of the Basis Pursuit problem: \begin{align*} \text{The \lambda Form:} & \quad && \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} \\ \text{The \epsilon Form:} && \quad & \arg \min_{x} {\left\| x \right\|}_{1} \\ & \text{subject to} && \frac{1}{2} {\... 3 One of the motivations to use the {L}_{2} norm comes from the Maximum a Posteriori Estimation (MAP) framework. If you model \psi \left( u \right) \sim \mathcal{N} \left( 0, \alpha \right) then if you derive the MAP Estimator in case the added noise is Gaussian you'd get the exact model you posted above. An example of the derivation of MAP model to ... 3 It is easier to prove it by using atoms. The 1st atom is the Absolute Value function \left| \cdot \right| which is convex. Then you have linear operation by the subtraction which is convex (Also concave). Then you linear combination which is also Convex. Hence the function is Convex. 3 Could it be that you are indeed looking for the closest orthogonal matrix Y? Then, there is a solution which involves computing the square root of D^TD . If E=(D^TD)^{1/2} were invertible, the solution would be its inverse. Yet, it is not invertible here. Then, there is a trick. If I remember well, you have to perform an eigenvalue/eigenvector ... 3 Assuming we know how to solve: \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + {\left\| E \boldsymbol{x} \right\|}_{1} $$For any matrix E one could see that:$$ \boldsymbol{w} \circ D \boldsymbol{x} = \operatorname{Diag} \left( \boldsymbol{w} \right) D \boldsymbol{x} = E \boldsymbol{x}$Where$ \...

2

Added: if $f(x) = \ell_1(x) = \sum |x_i|$, the terms are all independent — as @Alejandro points out, you can just minimize each term by itself. It's more interesting to minimize $\qquad\qquad$ $\| Ax - b \|_2^2 + \lambda \|x\|_1$ where $\|x\|_1$ instead of $\|x\|_2$ is intended to push many $x_i$ to 0. The following notes are for this case. (I ...

Only top voted, non community-wiki answers of a minimum length are eligible