Tag Info

13

"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 is no consensus, yet there are some worthy contenders. The first option "count only non zero terms" is precise, but inefficient (sensitive to ...

7

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 Deconvolution. In general blind deconvolution is ill poised problem. So we need to make assumptions about the model. The more assumptions the better the chance ...

6

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 Sub Gradient / Sub Derivative. When you integrate Sub Gradient instead of Gradient into the Gradient Descent Method it becomes the Sub Gradient Method. In the ...

6

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 \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}^{2} + \lambda {\left\| \boldsymbol{x} \right\|}_{1}$$ Where the ${L}_{1}$ norm is sparsity inducing regularization ...

5

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(\... 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, ... 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 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 $) and generated by a Gaussian Random Vector. Now, let's create$ N $random vector$ {\left\{ {r}_{i} \right\}}_{i = 1}^{N} by: $${r}_{i} = A {g}_{i}$$ ... 5 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 \end{align*} Where {\left\| \cdot \right\|}_{0} $is the Cardinality Measure which counts the number of non zero elements in the argument. The above is NP ... 4 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 indeed what you need is to create the DFT matrix of zero padded signal and take the subset which you're interested in as you wrote in your question. If you define ... 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 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 values. In fact, the situation with negligible vs significant values which is not strictly sparse is often referred to as "compressible", see e.g. ... 3 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-to-sine signals. Conversely, a zero signal, except for a few values, is sparse in its original domain. In narrow sense, a sparse representation of data is a ... 2 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 invariant: a signal and its scaled versions possess the same sparsity index, as they have the same quantity of zero values. I have been thinking a lot about ... 2 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$Ψ$, why don't we just measure$z=Ψ^{−1}x=Ψ^{−1}Ψα=a$, and store the value and index of the non-zero components of$z (=α)$? Compressive Sensing as the name ... 2 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 parameters, degrees of freedom) is much lower than the inherent dimension of the object. For instance, let us first consider 1.000.000 points$(x_i,y_i)$, acquired to ... 2 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 targets, or a small number of moving targets. Radar tomography - This application uses multiple radar passes at slightly different elevations to extract elevation ... 2 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 only with lossy compression. When one considers the original data as the "clean" reference, lossy compression adds a amount of loss related (generally vaguely ... 2 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 isn't. This means that when calculating your sparse representation from the noisy signal, you will only capture the clean signal, and not the noise. 2) ... 2 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 start time$t_{B_k}$of duration$n_{B_k}$. For one impulse response this is shown in their figure 1(b). The overall sparsity will depend on the reflections and ... 2 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 reconstruction we use sparsity assumption to reconstruct the signal through solving problems of this form (there are other forms of solution): $$\min|x|_1 s.t. |\Phi ... 2 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 toolbox, you could try to find a free one or write a fit function by yourself (e.g. with fminsearch). However, this is not the fastest algorithm and also you would ... 2 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 matrix B as asked by the OP. In the compressive sensing setting, the coherence of a sensing matrix A is useful when we are using it for constructing ... 2 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, your signal is a "0-simple" signal, i.e. your values are either 0 or some constant. The problem can easily be scaled to 0 or "some constant" instead of 0 or 1.... 2 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_{\boldsymbol{x}} {\left\| \boldsymbol{x} \right\|}_{1} \mbox{ subject to } {\left\| A \boldsymbol{x} - \boldsymbol{y} \right\|}_{2}< \delta .$$In your 2nd ... 1 If the signal$x$is already sparse in the original/time domain, then it does not need to be transformed, in other words the transform$\mathcal{J}$can be taken to be the identity. So$x$and$X=\mathcal{J}x$are equal. What we want is to recover, from observed$y$, the unknown$x$, via the recovery of$X$, since$x=\mathcal{J}^{-1}X$. In that case,$A$is ... 1 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 process, and not a signal. You can think of a full characterisation of any kind of noise by means of a function$p: S \to \mathbb{R}^+_0 $that maps a signal$s$... 1 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 evaluate sub-gradients around points where elements of$\mathbf{x}$are zero. In fact most of the algorithms effectively treat elements below a certain threshold as ... 1 I haven't read the paper, but from the information you provided it appears the appropriate definition is the first one you gave, i.e., the "entrywise" matrix norm. The text you quoted refers to the norms being "elementwise" which is equivalent to being "entrywise". One way to look at this norm is as the$l_1\$ equivalent of the Frobenius norm. Essentially, ...

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