10 votes
Accepted

Why Does the Median Filter Minimize the Absolute Value Error $L_1$ Cost Function?

Given a set of values $ {\left\{ {s}_{i} \right\}}_{i = 1}^{N} $, we're basically after: $$ \arg \min_{x} \sum_{i = 1}^{N} \left| {s}_{i} - x \right| $$ One should notice that $ \frac{\mathrm{d} \left ...
user avatar
  • 40.7k
8 votes

How to Formulate a Constraint Which Ensures All Variables Have the Same Sign

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 ...
user avatar
  • 40.7k
8 votes
Accepted

Quadratic Programming with Linear Equality Constraints

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{...
user avatar
  • 40.7k
8 votes
Accepted

Adding Variance \ Weights Information When Solving a Basis Pursuit Denoising Problem (BPDN)

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 ...
user avatar
  • 40.7k
7 votes

Convex Optimization in Signal and Image Processing

Papers Interpolation by Solving an Optimization Problem. The Chebyshev Center Problem could be thought as Robust Localization Problem. Books Daniel P. Palomar, Yonina C. Eldar - Convex Optimization ...
user avatar
  • 40.7k
7 votes
Accepted

$ {L}_{0} $ Pseudo Norm Minimization in Compressive Sensing

the solution for a sparse recovery problem is given by: $$\text{min} ||x||_0$$ $$\text{s.t} \hspace{2mm} y = Ax$$ The definition of $||x||_0$ is no. of non-zero entries in $x$. ...
user avatar
7 votes
Accepted

How to Use the DFT (FFT) to Solve a Least Squares Regularization Problem (Inverse Problem)?

The question really depends on $ f \left( \cdot \right) $. Yet in order to show how to use FFT we can even use 1D signals. Let's rewrite the problem: $$ \hat{x} = \arg \min_{x} \frac{1}{2} \left\| K ...
user avatar
  • 40.7k
7 votes

Solving LASSO ($ {L}_{1} $ Regularized Least Squares) with Gradient Descent

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 ...
user avatar
  • 40.7k
7 votes
Accepted

Fastest Available Algorithm to Blur an Image (Low Pass Filter)

The fastest blur would be Box Blur. You can implement it using Running Sum. I think Intel FilterBoxBorder works in that manner. If you'd like you can do a few ...
user avatar
  • 40.7k
7 votes
Accepted

Resources on Solving Convex Optimization Problems in the Compressed Sensing Field

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 ...
user avatar
  • 40.7k
7 votes
Accepted

Convex Optimization with $ {L}_{1, 2} $ Regularization Term

The problem is given by: $$\begin{equation} \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} \...
user avatar
  • 40.7k
7 votes
Accepted

Super Resolution in Frequency Domain Using Compressed Sensing

You can employ Compressed Sensing / Sparse Representation for Super Resolution in Frequency Domain. One way to do so is solving the problem: $$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| F \...
user avatar
  • 40.7k
7 votes
Accepted

How to Solve Image Denoising with Total Variation Prior Using ADMM?

Formulation of the Denoising Problem The problem is given by: $$ \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda \operatorname{TV} \left( x \right) = \arg \min_{x} \frac{1}{2} {\...
user avatar
  • 40.7k
7 votes
Accepted

How to Solve Non Blind Image Deblurring with Total Variation Prior Using ADMM?

Formulation of the Problem I am solving the problem under the following assumptions: The blurring operator is Linear and Spatially Invariant (Hence applied by convolution). The blurring operator is ...
user avatar
  • 40.7k
7 votes
Accepted

Tikhonov Regularization for Complex Matrices

Usually Tikhonov Regularization is applied in the following form: $$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \frac{\lambda}{2} {\left\| \...
user avatar
  • 40.7k
6 votes
Accepted

Ideas on Matrix Factorization / Transformations for $ {L}_{1} $ Minimization

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 ...
user avatar
  • 40.7k
6 votes
Accepted

Convex Optimization in Signal and Image Processing

There's a whole area of signal processing dedicated to optimal filtering. In pretty much every case I've seen the filtering problem is formulated with a convex cost function. Here's a freely ...
user avatar
6 votes

What Is the Difference between RLS, LMS and Wiener Filter? When Is One Preferred Over Another?

All three are Estimators / Predictors. All of them try to estimate the coefficients of Linear Filter which minimizes an MMSE Cost Function. The Wiener filter assumes all data is given and sets the ...
user avatar
  • 40.7k
6 votes

Best Metric to Compare Sparsity of Vectors

I am sorry I cannot comment your answer due to my low reputation. Gini and your suggested sparsity ratio ($l_1(x)/l_2(x)$) both give me the same value for $\lambda$. But The problem I still see is ...
user avatar
  • 223
6 votes

Reference Code for Positive Basis Pursuit Denoising

I assume you're after the following optimization problem: $$\begin{align*} \arg \min_{x} \; & {\left\| x \right\|}_{1} \\ \text{subject to} \; & A x = b \\ & x \succeq 0 \end{align*}$$ ...
user avatar
  • 40.7k
6 votes
Accepted

Why use parametric based estimation methods - confusion regarding terms

Hi: I'll try to answer as briefly as possible and only with respect to statistics. not dsp. In statistics, if you have a nice pdf such as the normal distribution, then maximizing the likelihood is ...
user avatar
  • 1,082
6 votes
Accepted

Why Is Non Linear Least Squares Method from MATLAB and Alglib Gives Different Results on the Same Data?

When you solve Non Linear Least Squares problem of a non convex cost function the end solution (Which is guaranteed to be a Local Minimum) will depend on: Method of Minimization. Method Parameters. ...
user avatar
  • 40.7k
6 votes
Accepted

The Gradient Operator of a Vectorized Image in Matrix Form

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 ...
user avatar
  • 40.7k
6 votes
Accepted

Sparse Recovery Best Algorithms

Usually the classic problem is given by: $$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| x \right\|}_{0} \leq k \...
user avatar
  • 40.7k
6 votes

Derivative with respect to complex conjugate

That's a trick which you will also find in a DSP context, that's why I choose to provide an answer here. It is related to the Wirtinger derivative, and you can find more details about it in this ...
user avatar
  • 80.2k
6 votes
Accepted

Solving LASSO (Basis Pursuit Denoising Form) with LARS

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 {\...
user avatar
  • 40.7k
6 votes
Accepted

Generate the Matrix Form of 1D Convolution Kernel

The way to build the matrix is playing with indices of the signal data and the convolution kernel. For example: ...
user avatar
  • 40.7k
6 votes
Accepted

Solve Efficiently the 1D Total Variation Regularized Least Squares Problem (Denoising / Deblurring)

I will answer Total Variation Regularization: $$ \arg \min_{\boldsymbol{x}} f \left( \boldsymbol{x} \right) = \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}...
user avatar
  • 40.7k
5 votes

How to Smooth Gradient Estimates for Steepest Descent Optimization

In the Probabilistic settings we have many methods applied to the Stochastic Gradient Descent in order to decrease the variance of the Gradient Estimation (ADAM / RMS Prop / AdaDelta, etc...). The ...
user avatar
  • 40.7k
5 votes
Accepted

Lagrange Multipliers Optimization - Complex Functions

I found the following in Charles Therrien's "Discrete Random Signals and Statistical Signal Processing" in one of the Appendicies. Say you have the function $Q(a)$ you wish to minimize such that $C(a)...
user avatar
  • 2,686

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