Questions tagged [optimization]
The optimization tag has no usage guidance.
167
questions
25
votes
5
answers
20k
views
What Is the Best First Order IIR (AR Filter) Approximation to a Moving Average Filter (FIR Filter)?
Assume the following first order IIR Filter:
$$ y[n] = \alpha x[n] + (1 - \alpha) y[n - 1] $$
How can I choose the parameter $ \alpha $ s.t. the IIR approximates as good as possible the FIR which is ...
19
votes
6
answers
9k
views
Fit a Piecewise Linear Model to Data with Unknown Knots and Number of Segments
What is a robust way to fit piecewise linear but noisy data?
I'm measuring a signal, which consists of several almost linear segments. I'd like to atomatically fit several lines to the data to ...
19
votes
2
answers
2k
views
What Does Make an Error Surface Convex? Is It Determined by the Covarinace Matrix or the Hessian?
I am currently learning about least-squares (and other) estimations for regression, and from what I am also reading in some adaptive algorithm literatures, often times the phrase "... and since the ...
15
votes
1
answer
869
views
Will an Unscented Kalman Filter Be "As Good" as Other Optimization Algorithms for This Problem?
I want to calibrate a tri-axis magnetometer when a tri-axis gyroscope is also available.
I am fairly certain I can solve this problem using various optimisation algorithms, but I would prefer to use ...
14
votes
6
answers
23k
views
Compressive Sensing Through MATLAB Codes
I am new to the topic of compressed sensing. I read a few papers about it by R.Baranuik, Y.Eldar, Terence Tao etc. All these papers basically provide the mathematical details behind it, i.e., Sparsity,...
9
votes
1
answer
171
views
Ideas on Matrix Factorization / Transformations for $ {L}_{1} $ Minimization
I am starting with a typical $\ell_1$ basis pursuit problem:
$$
\min_{\mathbf{x}} \Vert \mathbf{x} \Vert_1 \quad \mathrm{s.t.} \quad \Vert \mathbf{ERx} - \mathbf{y} \Vert_2 \leq \epsilon,
$$
where $\...
9
votes
1
answer
451
views
Weighted Nuclear Norm Minimization for Image Denoising
Recently, I saw new published papers like
Shuhang Gu, Lei Zhang, Wangmeng Zuo, Xiangchu Feng, Weighted Nuclear Norm Minimization with Application to Image Demonising [pdf].
about denoising images ...
8
votes
1
answer
2k
views
Adaptive filtering: Optimum filter length and delay
I'm trying to find the optimum filter length for an Adaptive Filtering, using RLS Algorithm.
I'm using this design:
So the "error" signal is the signal without noise (and that's the signal that I ...
7
votes
3
answers
7k
views
Derivative with respect to complex conjugate
I have a real function $C$ of a complex vector $x$. While taking the gradient of the function $C$ for minimising the same, why do we take the derivatives with respect to the complex conjugate of $x$, ...
7
votes
5
answers
581
views
Curve Fit of Step Function with Boundary on the 2nd Derivative
Consider this step function:
The signal that "fits" this should look like the following (in green):
The corners are now smooth because the maximum second derivative allowed is not infinite anymore.
...
7
votes
2
answers
728
views
Convex Optimization in Signal and Image Processing
In signal processing, convex optimization plays a useful role in problems such as sparse signal recovery and filter design. What other places does convex optimization appear?
For example, in ...
7
votes
2
answers
1k
views
Why Is Non Linear Least Squares Method from MATLAB and Alglib Gives Different Results on the Same Data?
i'm trying to rewrite my Matalab prototype for some DSP to C++ and encountering a displeasing problem. I'm trying to fit data to a function $y = a * (\pi / 2 + arctg(b * x))$. In Matlab it works well ...
7
votes
1
answer
3k
views
What Is the Difference between RLS, LMS and Wiener Filter? When Is One Preferred Over Another?
I'm dealing with a channel equalization problem where the channel is modeled as a WSS process.
I understand LMS utilities a Wiener-like approach, ie it converges to the optimal (wiener) solution.
I ...
6
votes
1
answer
189
views
Why Does the Median Filter Minimize the Absolute Value Error $L_1$ Cost Function?
I can easily prove that the mean filter minimizes the square error $L_2$ cost function using simple calculus.
However, how do you prove that the median filter is optimal with respect the absolute ...
6
votes
2
answers
743
views
Quadratic Programming with Linear Equality Constraints
I need to solve an equality constrained minimization problem as give below
$$\min_{\textbf{w}} \mathbf{w}^TR\mathbf{w} $$
such that
$$X\mathbf{w} = \mathbf{1}$$
where $R\in \mathbb{R}^{n\times n}$ is ...
6
votes
2
answers
422
views
Constrained Least Squares Filter Design
I would like to design a complex FIR filter, $h$, for a known signal that produces a desired output: $d$ = $s*h$ (where $s$ is my signal and $d$ is the desired filter output). Let $S$ be the ...
6
votes
2
answers
2k
views
How to Solve Image Denoising with Total Variation Prior Using ADMM?
I was looking at some articles or Wikipedia on denoising images using the Total Variation norm. The setup is the Rudin Osher Fatemi (ROF) scheme, and the corresponding equation is:
$$
F(u)=\int_{\...
6
votes
1
answer
1k
views
How to Formulate a Constraint Which Ensures All Variables Have the Same Sign
I'm trying to include a constraint in my problem (to be solved by any convex optimization solver). Let {a,b,c,d ...} be a finite set of continuous variables. How to formulate a constraint which ensure ...
6
votes
2
answers
731
views
Reference Code for Positive Basis Pursuit Denoising
I am trying to reconstruct a positive sparse signal using compressed sensing (friedlanders code), I cannot find a way to impose the positivity constraint for this implementation. I have seen some ...
6
votes
1
answer
985
views
How to Use the DFT (FFT) to Solve a Least Squares Regularization Problem (Inverse Problem)?
Let $X$ and $K$ be an image and a Point Spread Function (PSF), respectively.
The blurred image $B$ is obtained as follows
$$B = X * K$$
I want to solve the following general regularization problem
$$\...
6
votes
1
answer
530
views
Approximating $ {L}_{0} $ Norm Minimization with Non Linear Convex Inequality Constraints using Reweighted $ {L}_{1} $ Minimization
I have an optimization problem consisting of the $ {\ell}_{0} $ norm as the objective and a nonlinear (convex) constraint as well as a linear constraint. I am wondering if the reweighted $ {\ell}_{1} $...
6
votes
1
answer
186
views
Signal Reconstruction in Compressed Sensing with a Simple Vector Signal as an Example
While going through the different types of reconstruction algorithm as mentioned in Richard G. Baraniuk - Compressive Sensing - Lecture Notes (Also on DocDroid), I came to know that minimum $ {L}_{1} $...
5
votes
2
answers
1k
views
Best Metric to Compare Sparsity of Vectors
I solved the Basis Pursuit Denoising Problem looking for a sparse solution (I am in compressive sensing):
$$ {x}^{\ast} = \arg \min_{x} \left\{ \frac{1}{2} {\left\| A x - y \right\|}_{2}^{2} + \lambda ...
5
votes
1
answer
2k
views
Design $ {L}_{2} $ Norm Optimal Infinite Impulse Response (IIR) Filters
It is widely known that matching a FIR filter of fixed length to a band model is an unconstrained QP-problem. The MATLAB function firls() implements a solution to ...
5
votes
2
answers
504
views
Proximal Gradient Method (PGM) for a Function Model with More than 2 Functions (Sum of Functions)
I am currently working in signal reconstruction. I am trying to develop an algorithm where the user can plug any constraint to the main objective function (let's say chi2, least squares). I was trying ...
5
votes
1
answer
153
views
On the Measurement Matrix Used for Compressing Sensing
Assume we have a matrix $x$ of size $(8,8)$ where each column is considered to be sparse with degree of sparsity equals to $4$. it means that every column can have $4$ zeros and $4$ non-zeros values ...
5
votes
1
answer
372
views
Super Resolution in Frequency Domain Using Compressed Sensing
To be noted that I'm very new to this topic, I would like to understand the fundamentals of how to get Super Resolution in Frequency Domain estimation using the Compressed Sensing Model.
I am also ...
5
votes
1
answer
137
views
Convex Optimization with $ {L}_{1, 2} $ Regularization Term
I have an optimization problem such as follow:
$$\underset{X}{\operatorname{argmin}}\sum _s \left \| T_sX_{:,s} - Y_{:,s} \right \|^2_2 +\lambda\left \| GX \right \|_{2,1} \tag{1}$$
I have introduced ...
5
votes
2
answers
174
views
Orthonormal Dictionaries for Band Limited Signals
If $\mathbf{x} = [x_0, x_1, \ldots, x_{N-1}]^T$ is the time sampled input signal and $\mathbf{Y} = [Y_0, Y_1, \ldots, Y_{N-1}]^T$ is the Fourier transform of the input signal, then a linear ...
5
votes
1
answer
459
views
Is Sum of Absolute Value / $ {L}_{1} $ Norm of Differences Convex?
I'm not sure how to approach this exercise.
One idea is to derive it w.r.t z, show that there is a min-extremum at $z=f_k$ and then show that for each value from the right and the left of the loss ...
5
votes
1
answer
276
views
Solving LASSO (Basis Pursuit Denoising Form) with LARS
I'm now working on using LARS (Least Angle Regression) algorithm to solve a LASSO problem in Basis Pursuit Denoising form like:
\begin{align*}
\quad && \arg \min_{\beta}{\left\| y - X\beta \...
5
votes
0
answers
615
views
fit theoretical spectrum to simulated one
I have a bunch of simulated time series, for which I can compute the power spectrum. Generally, the simulated power spectrum can be sketched as follows:
I now aim to calculate the features of the ...
4
votes
2
answers
8k
views
Fastest Available Algorithm to Blur an Image (Low Pass Filter)
I am working with a camera that produces ugly artifacts:
by using ANY blur filter on the camera's output the visual quality improves drastically:
The above image was created using OpenCV's cv::...
4
votes
2
answers
3k
views
Solving LASSO ($ {L}_{1} $ Regularized Least Squares) with Gradient Descent
To the best of my knowledge, state of the art methods for optimizing the LASSO objective function include the LARS algorithm and proximal gradient methods.
I was wondering however, if the LASSO ...
4
votes
3
answers
333
views
Decomposing a DFT into multiple FFT calls
I'm using a good fast FFT implementation (vDSP) that will only work on power of 2 blocks of audio data. Now I have a problem where I would like to be able to apply the calculations to non powers of 2 ...
4
votes
1
answer
340
views
Gradient descent algorithm not converging
I wish to use the gradient descent algorithm to minimize the cost function
$$J(\mathbf{w}) = (\mathbf{w} - \mathbf{w}_{o})^{T} \mathbf{A}(\mathbf{w} - \mathbf{w}_{o})$$
where $\mathbf{w} \in \mathbb{R}...
4
votes
1
answer
102
views
Adding Variance \ Weights Information When Solving a Basis Pursuit Denoising Problem (BPDN)
Having a "measured" vector $\mathbf{y}$ with its statistics (counts or variance per element), one can use weighted least squares approach to solve the linear system $$\mathbf{A}\mathbf{x} = \...
4
votes
1
answer
370
views
Tikhonov Regularization for Complex Matrices
Tikhonov regularization is used to regularize ill-posed inverse problems if the matrix $A \in \mathbb{R}^{n,m}$ to be inversed has a high condition number. For example
$$
A=\begin{bmatrix}1&1\\
1&...
4
votes
1
answer
161
views
Resources on Solving Convex Optimization Problems in the Compressed Sensing Field
When I read papers of compressed sensing, sparse representation and whatever requiring optimization of a cost function, I just find the final results as an iterative equation or so which will converge ...
4
votes
1
answer
163
views
How to calculate signal which is not changed by a filter?
Suppose that there is a FIR filter F and a signal S. The filtered signal is the convolution of F and S, F * S.
The problem: how to calculate a signal S' such that F * S' = S' (the filtered version ...
4
votes
1
answer
157
views
Finding length of period in time domain data
I have a series of measurements of a signal source, which emits a periodic signal at an unknown interval time of p seconds. Detecting the signal is not easy so I am ...
4
votes
1
answer
149
views
Why Does FISTA Algorithm Not Work for Signed Signals?
Using the FISTA Algorithm for compressive sensing from Tiep H. Vu - FISTA, I created the matlab example below.
I created 2 sparse signals x_signed and x_pos, where the latter only contains positive ...
4
votes
1
answer
205
views
Sequential Non Linear Least Squares Problem
I have the the following non-linear function,
$$s(x;A_k,\mu_k,\sigma_k)=\sum_{k=1}^2 A_k \exp\left(\frac{-(x-\mu_k)^2}{\sigma_k^2}\right)$$
with unknown (but deterministic) parameters $A_k,\mu_k,\...
4
votes
1
answer
140
views
Sparse Recovery Best Algorithms
In the big data era, in order to control the cost, complexity, and bandwidth of collecting and processing high-dimensional data systems, it is critical to exploit models that ...
4
votes
1
answer
163
views
Converting Hadamard Product into Matrix Multiplication in Image Deconvolution with Total Variation (TV) Using ADMM
I would like to solve the following Image Deconvolution equation by ADMM.
$$\mathbf { \min\frac{1}{2}\Vert{Cx-b}\Vert_2^2+\Vert w\circ (D x)\Vert_1 \tag 1}$$
Where, $x$ is a vector of unknown pixel ...
4
votes
1
answer
185
views
How to Solve the Image Dehazing Problem Using ADMM?
I want to solve the image dehazing problem using ADMM.
I want to use the proximal algorithm to optimize each element.
I refer to this treatise: Efficient image dehazing with boundary constraint and ...
4
votes
1
answer
444
views
How to Solve an Image Deblurring Problem by Variational Methods Using ADMM?
Following up on a previous question, I wanted to understand how to solve an image deblurring problem using Variational methods in matlab or julia.
Given some original blurry image $f$, I would like to ...
4
votes
1
answer
1k
views
How Is Mixed Norm ($ {L}_{1, 2 }$) Better than $ {L}_{1} $ Norm for Sparse Representation?
Using $ {l}_{1} $-norm regularization for the purpose of achieving sparsity of the solution has been successfully applied a lot. But many times, I found the paper using mixed-norm instead of $l_1$-...
4
votes
1
answer
169
views
IMU Speed Tracking Through Known Path
I am new to signal processing and Kalman Filtering here. Thanks for your help.
I working with an IMU for a tracking project where the IMU moves throw a known path but at an unknown speed (within ...
4
votes
1
answer
141
views
How to regularize the latent variables of a kalman filter to be small?
This is perhaps a bit of a weird idea but suppose I want the latent variables of a Kalman filter to be small (like as if the states were being regularized). This is kind of like putting an extra prior ...