16
I agree that the windowing filter design method is not one of the most important design methods anymore, and it might indeed be the case that it is overrepresented in traditional textbooks, probably due to historical reasons.
However, I think that its use can be justified in certain situations. I do not agree that computational complexity is no issue ...
8
The LMS algorithm is based on the idea of gradient descent to search for the optimal (minimum error) condition, with a cost function equal to the mean squared error at the filter output. However, it doesn't actually calculate the gradient directly, as that would require knowing:
$$
E(\mathbf{x}[n]e^*[n])
$$
where $\mathbf{x}[n]$ is the input vector and $e[...
7
Windowed Sinc filters can be adaptively generated on the fly on processors barely powerful enough to run the associated FIR filter. Windowed Sinc filters can be generated in finite bounded time.
The generation of some simple windowed Sinc filters can be completely described (and inspected for malware, etc.) in a few lines of code, versus blind use of some ...
7
The play similar role in those algorithms - the ability to forget the past and adapt to current reality.
In the LMS, the classic implementation has $ \alpha = 1 $.
Namely the optimal weights at any point are function of all inputs.
The Leakage factor allows to weigh the past differently in a damped manner which over times means the far past has ...
7
Slope from all samples obtained
To summarize the question's problem, you want to calculate the slope based on all samples obtained thus far, and as new samples are obtained, update the slope without going through all the samples again.
On the page you cite is the equation for calculation of the slope $m_n$ that together with $b_n$ minimizes the sum of ...
6
To expand on what Peter K. has said, if the signals being used by the filter are stationary, then the filter weights or coefficients can be determined and the filter operates as it was designed without further updates to the filter weights. However, if the signals change, or become quasi-stationary, the filter will adapt continuously.
6
That really depends on context, but generally adaptive implies that the calculations are done on-line / on the fly.
In some applications, the filter is updated for a while, then the adaptation is turned off and the last lot of weights are used.
6
I'll show here one benefit of a windowed design and a trick to get the same benefit from Parks–McClellan.
For half-band, quarter-band etc. filters windowing retains the time-domain zeros of the scaled sinc function, which is the prototypical ideal low-pass filter. The zeros end up in the coefficients, reducing the computational cost of the filters. For a ...
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} + {\...
5
The idea is to represent all operation sing Matrices.
Once it is done, it is easy to solve the problems as a Least Squares problems.
The way to represent Convolution Operation using a Matrix is by Toeplitz Matrix.
For 1D it is pretty straight forward to do (Just pay attention to boundary).
So let's take the simple model in the comment:
$$ g = f \circ h + ...
5
Kalman filter is the best linear estimator regardless of stationarity or Gaussianity. Also in the Gaussian case it does not require stationarity (unlike Wiener filter). In the linear Gaussian case Kalman filter is also a MMSE estimator or the conditional mean.
5
While I completely agree with Jason R's answer, I would like to add a few things that I consider important. First of all, it is a misunderstanding to believe that for least squares designs the transition band width is smaller than for equi-ripple designs. The width of the transition band depends on many design parameters but it is independent of the ...
5
For anyone who is interested, i coincidentally found a paper describing the method implemented in matlab's filtfilt.m. A link to the paper is attached. At least to my understanding matlab's filtfilt.m doesn't implement the Gustafson algorithm.
Sadovsky, P.; Bartusek, K: Optimisation of the Transient Response of a Digital Filter, Radioengineering Vol. 9, No. ...
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
The Jacobian is not computed numerically but analytically and then just evaluated. The frequency response of the IIR filter is
$$H(e^{j\omega})=\frac{b_0+b_1e^{-j\omega}+\ldots+b_Me^{-jM\omega}}{1+a_1e^{-j\omega}+\ldots+a_Ne^{-jN\omega}}=\frac{B(e^{j\omega})}{A(e^{j\omega})}\tag{1}$$
Now you need the derivative with respect to the filter coefficients:
$$\...
5
One way to interpret the Tikhonov Regularization is using the Maximum A Posteriori (MAP) framework.
Lets' say we have a model of the form:
$$ \boldsymbol{y} = H \boldsymbol{x} + \boldsymbol{n} $$
Where $ \boldsymbol{n} \sim N \left( 0, {\sigma}_{n}^{2} \right) $, namely Additive White Gaussian Noise, and the prior knowledge about $ \boldsymbol{x} $ is $ \...
4
Here's the way I think about a discrete Wiener Filter
Consider a sequence of observations $\mathbf{y} \in \Re^n $
Form a matrix from the input $\mathbf{x} \in \Re^{n+r-1}$ by shifting columns one sample each:
$$
X= \begin{bmatrix}
x_1 & x_2 & ... & x_r \\
x_2 & x_3 & & x_{r+1} \\
x_3 & x_4 & & x_{r+2} \\
... & &...
4
I suggest this reference regarding the comparison between least-squares and Kalman filters :
Fundamentals of Kalman Filtering: A Practical Approach by P. Zarchan & H. Mussof
Especially Chapter 3 (Recursive Least-Squares Filtering) and Chapter 4 (Polynomial Kalman Filters).
In Chapter 4, the authors show that the discrete (time) n-th order polynomial ...
4
A lot has been said already, allow me to add some comments:
Kalman filters are an application of Bayesian probability theory, which means that "a priori information" or "prior uncertainty" can (and must) be specified. As I understand, this is not the case with traditional least-squares fitting. While observations (data) can be weighted with probabilities in ...
4
You can always augment the matrices to do so.
Let's assume the first model is given by:
$$ {y}_{1} = {H}_{1} * {\theta}_{1} $$
The second model is given by:
$$ {y}_{2} = {H}_{2} * {\theta}_{2} $$
The third model is given by:
$$ {y}_{3} = {H}_{3} * {\theta}_{3} $$
If we assume the number of parameters of the model are the same, namely $ {\theta}_{1}, {\...
4
It is basically an approach choice.
Inside the math is identical.
Usually, when doing Least Squares curve fitting, you're not looking for the Polynomial coefficients but a scaled version of them.
For instance, if you try to estimate Range, Velocity and Acceleration from Range Measurements using LS you need to scale the Polynomial Coefficients according to ...
4
If you want to solve for single value of $ \lambda $ in the model:
$$ \arg \min_{x} \frac{1}{2} {\left\| A x - b \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{1} $$
Then you can use Coordinate Descent method which is the fastest and simplest and doesn't require any matrix inversion.
I have a MATLAB code for in my $ {L}_{1} $ Regularized Least Squares ...
4
Since this is a linear model if you add noise which isn't centered (Non zero mean noise) your estimation will be good up to a bias term.
The easy way to do so is to remove the bias from $ y $ and solve.
In case you know the mean of the added noise, just remove it from your measurement and your model becomes the classic Linear Least Squares.
If you don't ...
4
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 ...
4
Least Squares solution is always well defined for Linear System of Equations.
In your case, which is under determined it means there are many solutions to the Linear Equations.
The Least Squares solution has nice property, it also minimizes the $ {L}_{2} $ norm of the solution (Least Norm Solution) hence it is well defined.
In practice, in order to solve ...
4
There is a package called FukuML.
In their description (Version 0.4.1) they write:
Support Vector Machine
Primal Hard Margin Support Vector Machine Binary Classification Learning Algorithm
Dual Hard Margin Support Vector Machine Binary Classification Learning Algorithm
Polynomial Kernel Support Vector Machine Binary Classification Learning Algorithm
...
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
This is closely related to Blind Deconvolution.
The only difference is we limit our self to a very specific type of blur kernels.
The nice thing about the Gaussian Kernel is being defined by single parameter - The Standard Deviation of the kernel.
The less nice thing is the connection isn't linear.
Optimization Problem
Let's define a classic non ...
4
There are really great answers.
I will try to give the Sequential Least Squares approach which generalizes to any Linear Model.
Sequential Least Squares Model
We're after solving the Linear Least Squares model:
$$ \arg \min_{\boldsymbol{\theta}} {\left\| H \boldsymbol{\theta} - \boldsymbol{x} \right\|}_{2}^{2} $$
Now imagine that we have new measurement ...
Only top voted, non community-wiki answers of a minimum length are eligible