# Tag Info

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 ...

8

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 ...

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

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  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 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 ...

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 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 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 Lecture Notes - Penalty and Shrinkage Functions for Sparse Signal Processing gives a good discussion of how the soft threshold function is derived. 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 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 ...

4

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 methods. I do not think injecting NaN gonna help, instead let's look at the ignored data as dimension reduction feature of CS. Here, the measurement matrix is basically an identity matrix that some of its ...

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 of $... 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 I cant add comment due to low reputation. I think you misunderstood @lennon310's meaning. I reviewed his answer in the link, he treated Phi as a row selection matrix. @lennon310, please consider change your word 'rectangular identity'. I know what you mean, but that is not called identity matrix. Phi (in his context) is something like 0 1 0 0 0 0 0 0 0 ... 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 ...

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