10 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 ...
user avatar
  • 39.3k
8 votes

Restricted Isometry Property (RIP) in Compressive Sensing

The restricted isometry property states that: $$\begin{equation} (1-\delta_S)||x||_2^2 \le ||A x||_2^2 \le (1+\delta_S)||x||_2^2 \end{equation}$$ for any $S$-sparse vector $x$. The restricted ...
user avatar
8 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 ...
user avatar
  • 39.3k
7 votes
Accepted

$ {L}_{0} $ Pseudo Norm Minimization in Compressive Sensing

the solution for a sparse recovery problem is given by: $$\text{min} ||x||_0$$ $$\text{s.t} \hspace{2mm} y = Ax$$ The definition of $||x||_0$ is no. of non-zero entries in $x$. ...
user avatar
7 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 ...
user avatar
  • 39.3k
7 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} \...
user avatar
  • 39.3k
7 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 \...
user avatar
  • 39.3k
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 ...
user avatar
  • 223
6 votes

Reference Code for Positive Basis Pursuit Denoising

I assume you're after the following optimization problem: $$\begin{align*} \arg \min_{x} \; & {\left\| x \right\|}_{1} \\ \text{subject to} \; & A x = b \\ & x \succeq 0 \end{align*}$$ ...
user avatar
  • 39.3k
6 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 \...
user avatar
  • 39.3k
6 votes
Accepted

Orthogonal Basis for a 2D Signals (Compressive Sensing)

If you have a function $ f \left[ m, n \right] \in \mathbb{R}^{M \times N} $ then the DFT of those functions is an orthogonal basis of functions in $ \mathbb{C}^{M \times N} $. So if we have: $$ F \...
user avatar
  • 39.3k
6 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 {\...
user avatar
  • 39.3k
5 votes
Accepted

Understanding Soft Thresholding Operator

The soft-thresholding function finds the minimizer of an objective function that involves data fitting in an $\ell_2$ sense as well as minimization of the $\ell_1$ norm (i.e. absolute value). The ...
user avatar
5 votes

Significance of $ \lambda $ in Basis Pursuit

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 {\left\| x \...
user avatar
  • 39.3k
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 ...
user avatar
  • 10k
5 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 ...
user avatar
  • 4,004
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 ...
user avatar
5 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 ...
user avatar
5 votes
Accepted

Orthonormal Dictionaries for Band Limited Signals

Why would you add the constraint of being Orthonormal Dictionary? It doesn't make sense in the context of what you ask. First we need to define resolution. If you mean the grid to be denser than ...
user avatar
  • 39.3k
5 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 ...
user avatar
  • 39.3k
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, ...
user avatar
  • 1,894
5 votes
Accepted

Reconstruction of a Signal from Sub Sampled Spectrum by Compressed Sensing

We're after the problem: $$\begin{aligned} \arg \min_{\boldsymbol{x}} \quad & {\left\| \boldsymbol{x} \right\|}_{1} \\ \text{subject to} \quad & \hat{F} \boldsymbol{x} = \boldsymbol{y} \end{...
user avatar
  • 39.3k
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. ...
user avatar
4 votes

Signal Reconstruction in Compressed Sensing with a Simple Vector Signal as an Example

Better is hard to measure unless there is a well defined measure. Yet in the classic Compressed Sensing model (Sparse Representation) the Holly Grail is actually the $ {L}_{0} $ Pseudo Norm. The ...
user avatar
  • 39.3k
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 ...
user avatar
  • 129
4 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 ...
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,...
user avatar
  • 1,894
4 votes

Compression Sensing for Blind Source Separation

I will sketch an idea how to use Sparse Represenattion (Dictionary Learning) for BSS. Let's say we have $ \mathcal{S} = \mathcal{S}_{1} \cup \mathcal{S}_{2} $ where $ \mathcal{S}_{1} = \left\{ {x}_{i}...
user avatar
  • 39.3k
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 ...
user avatar
4 votes
Accepted

Implementation of Block Orthogonal Matching Pursuit (BOMP) Algorithm

The Block Orthogonal Matching Pursuit (BOMP) Algorithm is basically the Orthogonal Matching Pursuit (OMP) Algorithm with single major difference - Instead of selecting single index which maximizes the ...
user avatar
  • 39.3k

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