8

As you have already pointed out in your question, it is not possible (without using optimization methods) to compute an exact L2 solution for the frequency domain design problem of IIR filters due to the non-linear relationship between the filter coefficients and the error function. There is, however, a method which can come close and which transforms the ...


7

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$. This is also called the sparsity of the vector. i.e., we are asking for the sparsest solution $x$, that satisfies $y = Ax$. Consider the simplest case where $...


6

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 available book on the subject - Sophocles J. Orfanidis - Optimum Signal Processing.


6

Keep in mind, L1 is not the only approach to compressive sensing. In our research, we've had better success with Approximate Message Passing (AMP). I am defining "success" as lower error, better phase transitions (ability to recover with fewer observations), and lower complexity (both memory and cpu). The Approximate Message Passing algorithm establishes ...


6

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 passes of it to approximate the Gaussian Blur. You can also use IIR Filter Coefficients to blur the image quite easily. You may have a look at my project Fast Gaussian Blur.


6

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 answer over at math.SE. In practice this trick is often used to compute the extremum (minimum or maximum) of a real-valued function depending on a complex variable (...


6

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


6

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} \frac{1}{2} \sum_{k} {\left\| {T}_{k} {X}_{:, k} - {Y}_{:, k} \right\|}_{2}^{2} + \lambda \sum_{l} {\left\| G {X}_{:, l} \right\|}_{2} \end{equation}$$ In the ...


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

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 | x \right | }{\mathrm{d} x} = \operatorname{sign} \left( x \right) $ (Being more rigorous would say it is a Sub Gradient of the non smooth $ {L}_{1} $ Norm ...


6

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 known. There is a measurement noise. So the model is: $$ \boldsymbol{y} = H \boldsymbol{x} + \boldsymbol{n} $$ Where $ H $ is the matrix form of the blurring ...


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

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

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 in Signal Processing and Communications. Stephen Boyd, Lieven Vandenberghe - Convex Optimization. Many of the exercises and examples are from the Signal / ...


5

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)=0$, where $C(a)$ may be complex valued and $a$ may be a complex vector. The constraint really represents two real-valued constraints. $$C_r(a)=0,\qquad C_i(a)...


5

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 way to calculate the optimal solution. The LMS and RLS are sequential / on line methods to solve the same problem and given the data is stationary they all ...


5

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 that I cannot take into account how well the vector is solving the equation $Ax-y$. I would like to combine the residuum $l_1(A\hat{x}-y)$ and the sparsity $l_1(\...


5

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 x - b \right\|_{2}^{2} + \frac{\lambda}{2} \left\| f \left( x \right) \right\|_{2}^{2} $$ The derivative is given by: $$ g = {K}^{T} \left( K x - b \right) + ...


5

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*}$$ This is pretty simple problem if we pay attention fo the fast that given $ x \succeq 0 $ then $ {\left\| x \right\|}_{1} = \boldsymbol{1}^{T} x $. This means ...


5

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 equivalent to minimizing the sum of squares of the residuals ( often called errors ). In other cases, where you either have a complicated distribution ( maybe ...


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

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

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

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 \end{align*}$$ Where $ {\left\| \cdot \right\|}_{0} $ is the Cardinality Measure which counts the number of non zero elements in the argument. The above is NP ...


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

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 \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{1} $$ Where the $ {L}_{1} $ norm is sparsity inducing regularization ...


5

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} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| D x \right\|}_{1} $$ Where $ D $ is the column stacked derivative operator. In the above I used the Anisotropic ...


5

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\| \boldsymbol{x} \right\|}_{2}^{2} $$ This formulation can be seen as: MAP Estimator with the prior of $ \boldsymbol{x} \sim N \left( 0, {\sigma}_{x}^{2} \right) $....


5

The way to build the matrix is playing with indices of the signal data and the convolution kernel. For example: function [ mK ] = CreateConvMtx1D( vK, numElements, convShape ) % ----------------------------------------------------------------------------------------------- % % [ mK ] = CreateConvMtx1D( vK, numElements, convShape ) % Generates a Convolution ...


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