18
L1magic. This is the toolbox associated with the original paper.
CompSens. This looks like it's in C, but you could possibly call it with mex -- not sure.
Model-based compressive sensing toolbox.
Most of the code is plain Matlab code
Each folder in the package consists of a CS recovery algorithm based on a particular signal model, and a script that ...
10
Like @sansuiso said, compressed sensing is a way of acquiring signals that happens to be efficient if the signals are sparse or compressible.
Compressed Sensing is efficient because signals are multiplexed, hence the number of multiplexed samples (called measurements) is smaller than the number of samples required by Shannon-Nyquist where there are no ...
8
Just to restate everything for clarity, the Compressed Sensing problem is defined as the following: given a signal $x$ of length $N$, we measure the projection of $x$ by some projection operator, $\Phi$ of size $M \times N$,
$$ y = \Phi x,$$
where $y$ is are our $M$ measurements of the original signal. We could also state this in terms of the inner ...
8
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 isometry constant is $\delta_S$, $0 < \delta_S < 1$.
This means that the matrix $A$ is guaranteed to only change the length of any vector $x$ "very little" as ...
7
In the case of general Compressed Sensing, we assume that we have no prior information about the location of the sparse support of a given signal. If we knew the support exactly, that is, if an oracle told us where the non-zero coefficients are located, we would only need $K$ measurements to recover our signal accurately. Since we do not generally have such ...
7
There are two things here: sparsity and compressed sensing.
Sparsity is a general hypothesis, just claiming that most of the energy of a signal is stored in a small number of coefficients in the good basis. This is quite intuitive, looking at Fourier transforms or wavelet transforms. It is true for probably any signal of interest (image, sound...) and ...
7
I suppose I am answering off-topic here then, but for L1-optimization approaches, I find YALL1 (http://yall1.blogs.rice.edu/) and SPGL1 (http://www.cs.ubc.ca/~mpf/spgl1/) very useful and efficient packages. TFOCS (http://cvxr.com/tfocs/) is probably a bit harder to use, but should be quite flexible. There is also CVX (http://cvxr.com/cvx/) which makes it ...
7
The Nyquist criteria refers not to the frequency, but to the bandwidth, which is related to information density in a signal. A very high frequency signal, of approximately known frequency, with a sufficiently small bandwidth, will still be aliased or folded down with baseband frequencies by undersampling. But if the bandwidth (or other known ...
6
Keep in mind, L1 is not the only approach to compressive sensing. In our research, we've had better success with Approximate Message Passing (AMP). I am defining "success" as lower error, better phase transitions (ability to recover with fewer observations), and lower complexity (both memory and cpu).
The Approximate Message Passing algorithm establishes ...
6
I'm by no means an expert in this, but I find the subject of compressed sensing very interesting, so I thought it'd be fun to play around with this.
I believe your error is in the generation of your sampling matrix, $\Phi$. According to the paper you reference "The convergence of this algorithm was proven in [1] under the condition that $\|\Phi\|_2 < 1$ ....
6
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$. This is also called the sparsity of the vector.
i.e., we are asking for the sparsest solution $x$, that satisfies $y = Ax$.
Consider the simplest case where $...
5
You may also want to check the Matlab UNLocBox: http://unlocbox.sourceforge.net
There are 4 compressive sensing scripts on the demo page: http://unlocbox.sourceforge.net/doc/demos/index.php
5
"Recovery of Exact Sparse Representations in the Presence of Bounded Noise", by J. Fuchs, deals with the case you ask. From the abstract:
The purpose of this contribution is to extend some recent results on sparse representations of signals in redundant bases developed in the noise-free case to the case of noisy observations. [..] We consider the case $b =...
5
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 thinking about the problem which I have tried to address to an extent and I would be happy to modify the response in light of more information.
In machine ...
5
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 signal can be recovered from very few linear measurements. In symbols, if $\mathbf x$ is $N\times 1$ sparse$^\ddagger$ vector, and $\mathbf A$ is an $M\times N$ ...
5
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 definition of the term in the context of dictionary learning, for example in K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation, ...
4
Indeed, there are ways in which sparsity, or information content, may be estimated
at the acquisition device. The details, practicality, and actual usefulness of doing so
is debatable and heavily dependent upon the context in which it is applied. In the case
of imaging, one could determine areas of an image which are more or less compressibile
in a ...
4
Problems such as those are closely related to "inverse problems", whereby one attempts to reconstruct a signal from an under-determined system of equations, (ill-posed problems) given some apriori information. As @Hilmar mentioned, you cannot reconstruct phase information from the absolute magnitude of a DFT, unless you have prior information that constrains ...
4
I am trying to answer your question about incoherence here rather than update my previous answer on another question of yours.
Compressive sensing requires low coherent pairs. So the lower $\mu(\Phi,\Psi)$, the better. Actually is $\Phi$ is spike basis (identity matrix) with $\phi_k(t) = \delta(t-k)$, and $\Psi$ is Fourier basis with $\psi_j(t) = 1/\sqrt n ...
4
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 predefined, e.g. FFT,DCT or can be learned from the image, e.g. sparse coding.
Here are a few well know example of algorithms that uses the sparsity assumption on ...
4
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 that I cannot take into account how well the vector is solving the equation $Ax-y$. I would like to combine the residuum $l_1(A\hat{x}-y)$ and the sparsity $l_1(\...
4
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 take measurements in a universal manner without knowing the dictionary $\Psi$ beforehand, if you choose the measurement matrix $\Phi$ as a sufficiently random ...
3
If you have your sensing matrix $\Phi$ and your representation matrix $\Psi$ you just need to calculate
where $\mu$ is your incoherence property and n is the number of elements in the signal.
$\Psi$ is you Fourier matrix and $\Phi$ is your sensing matrix (your A matrix). In matlab you can just calculate the maximum inner product from the n-length vectors ...
3
The mutual coherence is a kind of proxy for the Restricted Isometry Constant (RIC), because the RIC is impractical to calculate i.e. NP hard. You should note that the RIP is sufficient but not necessary for sparse reconstruction.
Here's another definition of mutual coherence - assume that you are trying to solve
$$y=Ax$$
where $x$ is sparse.
The mutual ...
3
Say you have measurements $y=Ax$, with a basis $\Psi$, and $A\in\mathbb R^{M\times N}$. Then we can write $y=A\Psi\hat x=\Phi\hat x$.
I then believe direct computation of the coherence requires us to solve
\begin{equation}
\mu = \max_{i<j} \frac{| \langle \Phi_i,\Phi_j\rangle |}{\| \Phi_i\|\| \Phi_j\|}
\end{equation}
where $\Phi_i$ is the $i$-th column ...
3
As @hotpaw2 explains, the Nyquist criterion has to do with the bandwidth of the signal, not the highest frequency as such. But if you do not know the exact frequency of the sampled signal (e.g. 40Hz) and only know that it is somewhere in a frequency range (e.g. 0-1000Hz), you in principle have to sample above 2000Hz (according to Nyquist) in order to be sure ...
3
Yes, it is possible to sample and reconstruct a signal at sampling frequency lower than the Nyquist Criteria. For that, the signal has to be sparse in some representation basis. Then it is absolutely possible to reconstruct the signal with a certain probability in having an error in reconstruction. Please refer to Terrence Tao's work in this regard.
As far ...
3
It seems your problem is that you don't have enough measurements ($n$ is too large) or, conversely, your sparsity level is too large ($k$ is too large).
I get the following results running your code with n=650 and k=50:
iter# = 0 MSE = 0.00812474693295
iter# = 1 MSE = 0.00271708140753
iter# = 2 MSE = 0.000356259110511
iter# = 3 MSE = 6.21904907643e-05
iter#...
3
The constant C is usually left unspecified as it can be very hard to calculate. It is independent of the signal dimension, and results in Compressed Sensing are generally only concerned with big-O results, so it falls out when we say something like $m = \mathcal{O}(s \ln{(N/s)})$. The important part in this statement is the strong dependence on the ...
3
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). This discussion of shrinkage functions gives a good discussion of how the soft threshold function is derived.
Only top voted, non community-wiki answers of a minimum length are eligible
