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 ...
- 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 ...
- 1,242
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 ...
- 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$. ...
- 96
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 ...
- 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} \...
- 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 \...
- 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 ...
- 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*}$$
...
- 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
\...
- 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 \...
- 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 {\...
- 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 ...
- 2,880
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 \...
- 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 ...
- 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 ...
- 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 ...
- 1,242
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 ...
- 1,242
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 ...
- 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 ...
- 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, ...
- 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{...
- 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.
...
- 29.7k
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 ...
- 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 ...
- 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 ...
- 199
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,...
- 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}...
- 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 ...
- 1,242
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 ...
- 39.3k
Only top scored, non community-wiki answers of a minimum length are eligible