Skip to main content
6 votes

Why Do Most of The Papers Use the Frobenius Norm for Denoising?

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 ...
Marcus Müller's user avatar
5 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 ...
Royi's user avatar
  • 19.8k
5 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{...
Royi's user avatar
  • 19.8k
4 votes

Optimization of square matrix multiplied with another matrix to have the final result a unitary matrix

Could it be that you are indeed looking for the closest orthogonal matrix $Y$? Then, there is a solution which involves computing the square root of $ D^TD$ . If $E=(D^TD)^{1/2}$ were invertible, the ...
Laurent Duval's user avatar
4 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 ...
Royi's user avatar
  • 19.8k
3 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 ...
Royi's user avatar
  • 19.8k
3 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} \...
Royi's user avatar
  • 19.8k
3 votes
Accepted

On the Use of OMP Algorithm to Estimate Sparse Vector

Well, in your example, the channel isn't exactly sparse. It has been shown that $\ell_0$ minimization can recover any $K$-sparse vector $x$ from observations $\Phi x$ as long as $2K < {\rm spark}(...
Florian's user avatar
  • 2,463
3 votes

Proximal Gradient Method (PGM) for a Function Model with More than 2 Functions (Sum of Functions)

Our goal is to obtain proximal operator of the following function $$ g \left( x \right) = {\left\| x \right\|}_{1} + \operatorname{TV}(x). $$ The involved optimization problem for any $z \in \mathbb{...
Mahesh Chandra Mukkamala's user avatar
3 votes
Accepted

Difference Between Iteratively Reweighted Least Squares (IRLS) and Sequential Quadratic Programming?

SQP is a method for solving smooth (objective and constraint functions are at least twice differentiable) constrained nonlinear optimization problems. It solves a series of quadratic programming ...
Brian Borchers's user avatar
3 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 ...
Royi's user avatar
  • 19.8k
3 votes

Solving inverse problem using black box implementation of the kernel

I will try to illustrate a solution. The general form of the problem is: $$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| \boldsymbol{h} \ast \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \...
Royi's user avatar
  • 19.8k
3 votes
Accepted

To find the unitary matrix which is the null of the results of multiplication with another matrix

Here is an attempt, tell me what I misunderstood. You say that $F\times F^{H}$ (which is of dimension $m\times m$ ) is unitary, which implies it is invertible. Therefore it means that $F$ is of full ...
NokiYola's user avatar
  • 507
2 votes
Accepted

Solving LASSO ($ {L}_{1} $ Regularized Least Squares) with Gradient Descent

Due to the non-smoothness of the $l_1$ norm, the algorithm is called subgradient descent. Because the you are looking for a solution that has a lot of zeros in it, you are still going to have to ...
David's user avatar
  • 2,871
2 votes

Why Do Most of The Papers Use the Frobenius Norm for Denoising?

There are many types of matrix norms. Three are quite standard: element-wise norms: unfolding the matrix into a long vector, and compute a norm for that vector. Schatten norms: (power) vector noms ...
Laurent Duval's user avatar
2 votes
Accepted

Least Angle Regression (LARS) without Matrix Inversion

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 ...
Royi's user avatar
  • 19.8k
2 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 ...
Royi's user avatar
  • 19.8k
2 votes
Accepted

Proximal Gradient Method (PGM) for a Function Model with More than 2 Functions (Sum of Functions)

Indeed the model for the Proximal Gradient Method (Also see Proximal Gradient Methods for Learning) is in the form of: $$ F \left( x \right) = f \left( x \right) + g \left( x \right) $$ Where usually $...
Royi's user avatar
  • 19.8k
2 votes
Accepted

Why Does FISTA Algorithm Not Work for Signed Signals?

I will try explaining why would someone use such an option as defining the solution as positive. The Proximal Gradient Method which is the hurt of the FISTA algorithm is basically a generalization of ...
Royi's user avatar
  • 19.8k
2 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 ...
Royi's user avatar
  • 19.8k
2 votes
Accepted

Automatic Image Enhancement of Images of Scanned Documents (Auto Whitening)

Their intention is to solve: $$ \arg \min_{ J \left( x, y \right) } \sum_{x, y} \left\| J \left( x, y \right) - 255 \right\|_{2}^{2} + \lambda \sum_{x, y} \left\| \nabla J \left( x, y \right) - \nabla ...
Royi's user avatar
  • 19.8k
2 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 {\...
Royi's user avatar
  • 19.8k
2 votes
Accepted

Fast Optimization for Long FIR Filters

Sampling will be at about 1 GHz, output should be about 10 kHz So, you're decimating by a factor of $10^5=2^5\cdot5^5$. This very much says that you'd normally go ahead and successively decimate. ...
Marcus Müller's user avatar
2 votes
Accepted

Is Sum of Absolute Value / $ {L}_{1} $ Norm of Differences Convex?

It is easier to prove it by using atoms. The 1st atom is the Absolute Value function $ \left| \cdot \right| $ which is convex. Then you have linear operation by the subtraction which is convex (Also ...
Royi's user avatar
  • 19.8k
2 votes

Optimization of square matrix multiplied with another matrix to have the final result a unitary matrix

If D is not singular, i.e. $\operatorname*{det}(D) \ne 0$ than simply $C = D^{-1}$ will do the trick, since $D \cdot C = I$, which is obviously unitary. If D is singular, i.e. $\operatorname*{det}(D) =...
Hilmar's user avatar
  • 45.7k
2 votes
Accepted

Solving a Weighted Basis Pursuit Denoising Problem (BPDN) with MATLAB / CVX

A MATLAB code which implements the problem as defined and solve it using CVX is given by: ...
Royi's user avatar
  • 19.8k
2 votes

Consistent reconstruction of image from partial images

OK, This is a really nice problem. To illustrate the problem with your approach above. I will do that in 1D so it converges to the mean. Imagine the following data at some part of the grid: The ...
Royi's user avatar
  • 19.8k
2 votes

Fit Data Samples with a Robust Fit

A simple and cheerful approach is to solve regular LMS for the sequence using different subsets of the total sample set, then pick the model that best satisfies some fitting criterion for the entire ...
Knut Inge's user avatar
  • 3,462
1 vote
Accepted

Converting Hadamard Product into Matrix Multiplication in Image Deconvolution with Total Variation (TV) Using ADMM

Assuming we know how to solve: $$ \arg \min_{\boldsymbol{x}} \frac{1}{2} {\left\| C \boldsymbol{x} - \boldsymbol{b} \right\|}_{2}^{2} + {\left\| E \boldsymbol{x} \right\|}_{1} $$ For any matrix $ E $ ...
Royi's user avatar
  • 19.8k
1 vote
Accepted

time-domain channel estimation based on two vectors optimization

You specify that $T$ is known and invertible, so you know $X_1, X_2$, and then it's really trivial: $y[3]=[X_1,X_2]*[h_1, h_2]$, and $y[9]=[X_7, X_8] *[h_1,h_2]$; write that down as matrix system $$\...
Marcus Müller's user avatar

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