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 ...
- 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 ...
- 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{...
- 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 ...
- 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 ...
- 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$. ...
- 96
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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} \...
- 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 \...
- 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} {\...
- 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 ...
- 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\| \...
- 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 ...
- 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 ...
- 308
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 ...
- 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 ...
- 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*}$$
...
- 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 ...
- 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.
...
- 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 ...
- 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
\...
- 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 ...
- 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 {\...
- 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:
...
- 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\|}...
- 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 ...
- 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)...
- 2,686
Only top scored, non community-wiki answers of a minimum length are eligible