6 votes

Best Metric to Compare Sparsity of Vectors

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 ...
N8_Coder's user avatar
  • 223
6 votes

Compressive Sensing vs. Sparse Coding

As you correctly noted compressed sensing, compressive sampling, sparse sampling all mean the same thing. Some authors also call it sparse sensing. The idea behind compressed sensing is that a sparse ...
Atul Ingle's user avatar
  • 4,134
6 votes
Accepted

Why doesn't compressive sensing work for any signal?

You can measure and reconstruct such a 1-sparse signal as you describe in your question. The crucial misunderstanding here is, as @MBaz points out, that you have to know the basis $\Psi$. You can ...
Thomas Arildsen's user avatar
6 votes
Accepted

Universal Bases (Dictionary) for Image Compression

This is a great and interesting question. There are 2 ways to look at it, empirically and analytically. But before we start, a major detail is that when dealing with images we mainly talk about the ...
Royi's user avatar
  • 19.6k
5 votes

Alternative to Orthogonal Matching Pursuit (OMP) Algorithm

The main advantage of OMP is that the residual is orthogonal to the current solution. Let's say you select all $k$ columns from $A$ (also called atoms) at once and let us also presume that $A$ is an ...
Paul Irofti's user avatar
5 votes
Accepted

Relationship between information retrieval and source separation in signal processing

There are, a few discrepancies that might be making a difference here. My suggestion would be to edit the question for clarity. There are quite a few assumptions that lead to non-straightforward ...
A_A's user avatar
  • 10.7k
5 votes
Accepted

Compressive Sensing vs. Sparse Coding

A couple of reference works offer an exaplanation: A neurological interpretation described in Scholarpedia Stanford's Unsupervised Feature Learning and Deep Learning tutorial If we look at the ...
Thomas Arildsen's user avatar
5 votes
Accepted

Can compressed sensing be used instead of intepolation for missing values?

Yes, at least in the above case it is possible. Though it might not be computationally as cheap as other methods such as least squares based curve fitting. I do not think injecting NaN gonna help, ...
MimSaad's user avatar
  • 1,976
5 votes

Universal Bases (Dictionary) for Image Compression

As a complement to the neat answer by @Royi, I would add that "sparsity" is originally a heuristic principle in science, that applies well to many interesting really world data and problems. ...
Laurent Duval's user avatar
4 votes

Real world application of signal sparsity?

Sparsity concept is extensively being used in computer vision and image processing. The Idea is that natural image can be pretty sparse when it is transformed to different bases. this bases can be ...
DoronPor's user avatar
  • 139
4 votes

Alternative to Orthogonal Matching Pursuit (OMP) Algorithm

What you propose is actually being used in other algorithms. Your proposal corresponds to the first step of iterative hard thresholding. After the first step, the residual is updated, correlation ...
Thomas Arildsen's user avatar
4 votes

What are the practical constraints on designing Sensing matrix in compressed Sensing?

Checking for RIP of a matrix is an NP-Hard problem which means it is not computationally feasible to accomplish. RIP is used in matrix design mostly in theoretical aspects. Stealing @David 's comments,...
MimSaad's user avatar
  • 1,976
4 votes
Accepted

Terminologies - sparse channel, sparse input, compressed sensing

The term sparse, as you mention, refers to the fact that some "signal", usually represented by a vector $x$ contains mostly zero or negligible values and only a few non-zero or significant ...
Thomas Arildsen's user avatar
4 votes
Accepted

On the Measurement Matrix Used for Compressing Sensing

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 = \...
Thomas Arildsen's user avatar
4 votes
Accepted

Estimating Convolution Input Under the Assumption of Sparsity and Constant Non Zero Values Using Compressive Sensing Approach

Basically your problem is called Blind Deconvolution. It means we want to estimate both the operator and the input given the output. You model is Linear Time Invariant Operator so we have LTI Blind ...
Royi's user avatar
  • 19.6k
4 votes
Accepted

Room Impulse Response Domain of Sparsity

That's tricky. RIRs are NOT sparse in any obvious physical sense (time, frequency, etc). In fact they are insanely complicated with thousands of degrees of freedom. The amount of relevant physical ...
Hilmar's user avatar
  • 44.6k
3 votes

Best Metric to Compare Sparsity of Vectors

Norms like $\ell_p$, $p \ge 1$, or quasi-norms ($0<p< 1$) are all $1$-homogeneous: $\ell_p(\lambda x) = |\lambda|\ell_p( x)$. Which is not the case for the $\ell_0$ count measure, which is scale ...
Laurent Duval's user avatar
3 votes

What are the practical constraints on designing Sensing matrix in compressed Sensing?

When you say "practical constraints on designing the sensing matrix", it depends on whether you mean realising the sensing matrix in actual hardware. In that case, physical constraints probably ...
Thomas Arildsen's user avatar
3 votes
Accepted

Sensing matrix for compressed sensing

A sensing matrix maps input vector to measurement vector through linear wighted summation of input. What makes a specific matrix good, is application dependent. Now, both distributions more or less ...
MimSaad's user avatar
  • 1,976
3 votes

Compressive sensing: numerical generation of RIP matrices

You can't prove RIP through numerical exploration of all possible cases. If you are interested in numerical analysis I suggest to use Coherence instead, however Coherence is not as strong condition ...
MimSaad's user avatar
  • 1,976
3 votes

Compressive sensing: numerical generation of RIP matrices

Unfortunately, you cannot test for RIP this way. You calculate delta for one random s-sparse vector. The RIP condition must hold ...
Thomas Arildsen's user avatar
3 votes
Accepted

Seeking compressive sensing imaging demo in MATLAB

You can start with the Compressive Imaging Code code by J. Romberg, illustrating the paper "Imaging via Compressive Sampling". Another great source of information and codes is on Nuit Blanche.
Laurent Duval's user avatar
3 votes
Accepted

Why do we need deterministic measurement matrices in compressed sensing?

As far as I know there are two reasons: In sensing part: For practical implementation, usage of random matrices is hard, so people try to come up with simpler matrices that are fixed, this is thought ...
MimSaad's user avatar
  • 1,976
3 votes
Accepted

Reference Code for Positive Basis Pursuit Denoising

SparseLab should be able to solve the positivity-constrained problem: SparseLab (Stanford) - Seeking Sparse Solutions to Linear System of Equations. See Donoho & Tanner, "Precise ...
Thomas Arildsen'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

Energy of compressed signals

Without information on $Φ$, you can obtain almost anything, since $\lambda Φ$ could be a valid CS matrix as well. Generally, one imposes structure contraints, such as unit energy for their rows or ...
Laurent Duval's user avatar
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.6k
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.6k
3 votes
Accepted

Compressive Sensing with Square Measurement Matrix

It's important to clearly distinguish the terms Compressive Sensing (CS) and Sparse Signal Recovery (SSR). CS is about taking fewer measurements than what classical criteria such as Nyquist would ...
Florian's user avatar
  • 2,463
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

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