# Tag Info

## Hot answers tagged convex-optimization

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.

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

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} + {\... 4 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 ... 4 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} $... 4 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:... 4 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 ... 4 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 ... 4 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 ... 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 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 ... 3 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 ... 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 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 ... 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 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 ... 2 Let me rewrite the problem:$$ \arg \min_{x} \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \frac{\lambda}{2} {\left\| L x \right\|}_{2}^{2} $$In order ot 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 ... 2 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} {\... 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 ... 2 There are many types of matrix norms. Three are quite standard: element-wise norms: unfolding the matrix into a long vector, and compute a norm for that vector. Schatten norms: (power) vector noms over singular values of the matrix. induced norm: maxima over vector norms with uni-norm vectors. The Frobenius norm is the most simple: the square root of the ... 2 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 ... 2 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 ... 2 Sampling will be at about 1 GHz, output should be about 10 kHz So, you're decimating by a factor of$10^5=2^5\cdot5^5. This very much says that you'd normally go ahead and successively decimate. In an FPGA, halfband filters are especially cheap and efficient to implement; better yet: they're extremely easy to design, and you don't have to change the ... 2 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} {\... 2 The Error in the Model The problem is in the dimensions of the Linear Operator A in your model compared to the Data Matrix X . The number of columns of the matrix A must match the number of pixels in each column of X (Each image). While in your case it matches the number of images. Matrix Form of 2D Linear Operator Let's try to build the ... 2 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. 1 I will give you a hint: you can first relax this problem to be a convex optimization problem by editing the second constraint asXw <= \vec{1}$$where the inequality is elementwise, then form the dual problem or the lagrangian as it is known popularly$$ w^TRw + \lambda^T(Xw -1) \tag{1}$$where$$\lambda <=\vec{0}$$Differencate (1) with respect ... 1$$ J(h) = \int_{R^+UR-}|e^Th-F_d|^2d\omega\tag{1}\\ = \int(e^Th-F_d)^H(e^Th-F_d)d\omega\\ = \int((e^Th)^H(e^Th) + F_d^HF_d -(e^Th)^HF_d - F_d^He^Th)d\omega\\ = h^H(\int(e^T)^He^Td\omega) h + \int |F_d|^2d\omega -\int (2 Re\{(e^Th)^HF_d\})d\omega$The second term in above integral is the integral of$L_2$norm of$F_d$in the region$R^+ U R^-$. Since$F_d(...

1

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 ...

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