Skip to main content
Share Your Experience: Take the 2024 Developer Survey
15 votes
Accepted

What is an exact measure of sparsity?

"Is there any exact, i.e. numerical, definition for sparsity?" And by numerical, I understand both computable, and practically "usable". My take is that: not yet, as least, there ...
Laurent Duval's user avatar
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
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
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
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

What exactly is "sparse representation"?

Take a sine-like signal $s$. In the appropriate Fourier $\mathcal{F}$ domain, it is represented by two "peaks", the other coefficients being zero. Fourier is a sparse representation for sines or close-...
Laurent Duval'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.7k
4 votes
Accepted

Differences Between Two $ {L}_{1} $ Norm Minimization Schemes

The first equation you have is often called the Quadratic Problem, which through the use of Duality can be shown to be equivalent to the Basis Pursuit De-Noising (BPDN) given as: $$ \arg \min_{\...
David's user avatar
  • 2,871
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
  • 45.3k
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.7k
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.7k
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
Accepted

Super Resolution in Frequency Domain Using Compressed Sensing

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 \...
Royi's user avatar
  • 19.7k
3 votes

Why is incoherence important for compressive sensing?

It is necessary when reconstruction is considered. Simply imagine the case when $A = \Phi \Psi$ has a high coherence, e.g. all columns are exactly the same and indistinguishable, then there is no ...
MimSaad's user avatar
  • 1,976
2 votes
Accepted

Is the basis of the sparse signal assumed known in compressed sensing?

Compressive Sensing is an approach to reconstruct sparse signals from incomplete set of measurements. In doing so, we need to know $Ψ$ to recover $x$, don't we? yes, we do. But if we know $Ψ$,...
MimSaad's user avatar
  • 1,976
2 votes
Accepted

Real world application of signal sparsity?

Sparsity covers a wide range of concepts. It characterizes an object (a signal, a system, a function) for which their exists a representation (exact or approximate) whose dimension (number of ...
Laurent Duval's user avatar
2 votes

Real world application of signal sparsity?

A couple of example areas: Sonar beamforming - in many cases there are a small number of targets Radar processing - a radar image can be decomposed to a background and sparse set of point like ...
David's user avatar
  • 2,871
2 votes
Accepted

sparse representation for image denoising

I will start the explanation from the compression viewpoint. There are two main types: lossless compression, and lossy compression. Noise, at least divergence or loss from the original data, arises ...
Laurent Duval's user avatar
2 votes

sparse representation for image denoising

Here are two interpretations of why sparse representations are useful for denoising: 1) Your clean image is well represented by your dictionary (usually a wavelet or 2D-DCT dictionary), but the noise ...
roygbiv's user avatar
  • 81
2 votes
Accepted

How to make the impulse response sparse? How does one know that the channel is sparse?

How you parameterize your sparsity will depend on your application. The authors of that paper, in a paragraph on page 231 say: which is why they clump the coefficients together in $P$ blocks of ...
Peter K.'s user avatar
  • 25.8k
2 votes
Accepted

Does the use of a sparse basis in Compressed Sensing imply the need to have access to all the information beforehand?

It seems to me you have a little misassumption here. During the sampling only $\Phi$ matrix is applied to the signal $x$, which is resulted in measurements vector $y$, $y=Φx$ . Later, in ...
MimSaad's user avatar
  • 1,976
2 votes

Sparse Signal fitting in MATLAB, for a sinusoidal function with more than 8 terms?

MATLAB has a curve-fitting toolbox where you pass a function of your choice to the fit function. Hence, the number of terms is totally up to you in this case. If you do not have a curve-fitting ...
M529's user avatar
  • 1,736
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
Accepted

Sparse Recovery Best Algorithms

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

Coherence Calculation in Sparse Sensing

Update I would like to rephrase the original problem with slightly different notation and claim that there is no need to measure the coherence of the product of the circulant matrix A and the DCT ...
Shailesh Kumar's user avatar
2 votes

Is There a Sparse Representation for Noise?

The question of the existence of a sparse basis of noise is closely related to the question of the effective dimensionality of the noise subspace. First, it is important to realise that noise is a ...
Jazzmaniac's user avatar
  • 4,583
2 votes

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

You can approach this problem as a special case of the "$k$-simple bounded signal" class described in (Donoho & Tanner, 2010 - Precise Undersampling Theorems ), see page 2, Example 3. Particularly,...
Thomas Arildsen's user avatar
1 vote

Is There a Sparse Representation for Noise?

Let's think about it in a different way - Generate Noise from a Dictionary. Let's create a Dictionary $ A \in \mathbb{R}^{m \times n} $ where each of its rows is normalized (Has Euclidean Norm of $ 1 $...
Royi's user avatar
  • 19.7k

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