Tag Info

Hot answers tagged optimization

18

L1magic. This is the toolbox associated with the original paper. CompSens. This looks like it's in C, but you could possibly call it with mex -- not sure. Model-based compressive sensing toolbox. Most of the code is plain Matlab code Each folder in the package consists of a CS recovery algorithm based on a particular signal model, and a script that ...

8

I suppose I am answering off-topic here then, but for L1-optimization approaches, I find YALL1 (http://yall1.blogs.rice.edu/) and SPGL1 (http://www.cs.ubc.ca/~mpf/spgl1/) very useful and efficient packages. TFOCS (http://cvxr.com/tfocs/) is probably a bit harder to use, but should be quite flexible. There is also CVX (http://cvxr.com/cvx/) which makes it ...

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

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

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 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 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 ... 5 You may also want to check the Matlab UNLocBox: http://unlocbox.sourceforge.net There are 4 compressive sensing scripts on the demo page: http://unlocbox.sourceforge.net/doc/demos/index.php 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$amay be a complex vector. The constraint really represents two real-valued constraints. $$C_r(a)=0,\qquad C_i(a)... 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 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. 5 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 (... 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 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 Based in experimental tests with k in range (2 to 100) the best fit (sum squared error) gives a relation of alfa = 1/k^0.865 being k number of samples for MovAvg filter 4 As has been referenced in the comments already, you're describing a pulse-amplitude modulation (PAM) signal constellation. The problem, as you've framed it, seems to suggest the AWGN vector channel (where symbols are described using discrete values s_1, s_2, and so on), in contrast to the waveform channel, where symbols are expressed using waveforms that ... 4 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 / ... 4 In order to be able to choose an optimal value for the delay \Delta it's important to understand how the system works. The purpose of the delay is to decorrelate the desired signal s(n) and the signal component s(n-\Delta) at the input of the adaptive filter. This means that \Delta must be chosen such that the autocorrelation R_{ss}(k) of s(n) is ... 4 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(\... 4 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) + ... 4 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 ... 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 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 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 ... 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 ... 4 It is indeed possible to formulate this setting in terms of matrix-vector products. First, let us re-formulate your$x$(notice throughout that I use bold letters for vectors and matrices): $$x = \begin{bmatrix}\mathbf{x}_1 & \mathbf{x}_2 & \ldots & \mathbf{x}_8\end{bmatrix}$$ where$\mathbf x_k$is the$k$column of$x$. I define the vertically ... 4 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 ...

3

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 nice thing is to utilize them in deterministic settings. So for instance you can use Momentum which to Signal Processing guy will look just like applying IIR / AR ...

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