اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn Open Problem on Sparse Representations in Unions of Bases
139
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider sparse representations of signals from redundant dictionaries which are unions of several orthonormal bases. The spark introduced by Donoho and Elad plays an important role in sparse representations. However, numerical computations of sparks are generally combinatorial. For unions of several orthonormal bases, two lower bounds on the spark via the mutual coherence were established in previous work. We constructively prove that both of them are tight. Our main results give positive answers to Gribonval and Nielsens open problem on sparse representations in unions of orthonormal bases. Constructive proofs rely on a family of mutually unbiased bases which first appears in quantum information theory.
قيم البحث
اقرأ أيضاً
We address the exact recovery of a k-sparse vector in the noiseless setting when some partial information on the support is available. This partial information takes the form of either a subset of the true support or an approximate subset including w
rong atoms as well. We derive a new sufficient and worst-case necessary (in some sense) condition for the success of some procedures based on lp-relaxation, Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS). Our result is based on the coherence mu of the dictionary and relaxes the well-known condition mu<1/(2k-1) ensuring the recovery of any k-sparse vector in the non-informed setup. It reads mu<1/(2k-g+b-1) when the informed support is composed of g good atoms and b wrong atoms. We emphasize that our condition is complementary to some restricted-isometry based conditions by showing that none of them implies the other. Because this mutual coherence condition is common to all procedures, we carry out a finer analysis based on the Null Space Property (NSP) and the Exact Recovery Condition (ERC). Connections are established regarding the characterization of lp-relaxation procedures and OMP in the informed setup. First, we emphasize that the truncated NSP enjoys an ordering property when p is decreased. Second, the partial ERC for OMP (ERC-OMP) implies in turn the truncated NSP for the informed l1 problem, and the truncated NSP for p<1.
In the first part of the series papers, we set out to answer the following question: given specific restrictions on a set of samplers, what kind of signal can be uniquely represented by the corresponding samples attained, as the foundation of sparse
sensing. It is different from compressed sensing, which exploits the sparse representation of a signal to reduce sample complexity (compressed sampling or acquisition). We use sparse sensing to denote a board concept of methods whose main focus is to improve the efficiency and cost of sampling implementation itself. The sparse here is referred to sampling at a low temporal or spatial rate (sparsity constrained sampling or acquisition), which in practice models cheaper hardware such as lower power, less memory and throughput. We take frequency and direction of arrival (DoA) estimation as concrete examples and give the necessary and sufficient requirements of the sampling strategy. Interestingly, we prove that these problems can be reduced to some (multiple) remainder model. As a straightforward corollary, we supplement and complete the theory of co-prime sampling, which receives considerable attention over last decade. On the other hand, we advance the understanding of the robust multiple remainder problem, which models the case when sampling with noise. A sharpened tradeoff between the parameter dynamic range and the error bound is derived. We prove that, for N-frequency estimation in either complex or real waveforms, once the least common multiple (lcm) of the sampling rates selected is sufficiently large, one may approach an error tolerance bound independent of N.
Advances of information-theoretic understanding of sparse sampling of continuous uncoded signals at sampling rates exceeding the Landau rate were reported in recent works. This work examines sparse sampling of coded signals at sub-Landau sampling rat
es. It is shown that with coded signals the Landau condition may be relaxed and the sampling rate required for signal reconstruction and for support detection can be lower than the effective bandwidth. Equivalently, the number of measurements in the corresponding sparse sensing problem can be smaller than the support size. Tight bounds on information rates and on signal and support detection performance are derived for the Gaussian sparsely sampled channel and for the frequency-sparse channel using the context of state dependent channels. Support detection results are verified by a simulation. When the system is high-dimensional the required SNR is shown to be finite but high and rising with decreasing sampling rate, in some practical applications it can be lowered by reducing the a-priory uncertainty about the support e.g. by concentrating the frequency support into a finite number of subbands.
Let $sigma={sigma_{i}|iin I}$ be some partition of the set $mathbb{P}$ of all primes, that is, $mathbb{P}=bigcup_{iin I}sigma_{i}$ and $sigma_{i}cap sigma_{j}=emptyset$ for all $i eq j$. Let $G$ be a finite group. A set $mathcal {H}$ of subgroups of
$G$ is said to be a complete Hall $sigma$-set of $G$ if every non-identity member of $mathcal {H}$ is a Hall $sigma_{i}$-subgroup of $G$ and $mathcal {H}$ contains exactly one Hall $sigma_{i}$-subgroup of $G$ for every $sigma_{i}in sigma(G)$. $G$ is said to be a $sigma$-group if it possesses a complete Hall $sigma$-set. A $sigma$-group $G$ is said to be $sigma$-dispersive provided $G$ has a normal series $1 = G_1<G_2<cdots< G_t< G_{t+1} = G$ and a complete Hall $sigma$-set ${H_{1}, H_{2}, cdots, H_{t}}$ such that $G_iH_i = G_{i+1}$ for all $i= 1,2,ldots t$. In this paper, we give a characterizations of $sigma$-dispersive group, which give a positive answer to an open problem of Skiba in the paper.
Let x be a signal to be sparsely decomposed over a redundant dictionary A, i.e., a sparse coefficient vector s has to be found such that x=As. It is known that this problem is inherently unstable against noise, and to overcome this instability, the a
uthors of [Stable Recovery; Donoho et.al., 2006] have proposed to use an approximate decomposition, that is, a decomposition satisfying ||x - A s|| < delta, rather than satisfying the exact equality x = As. Then, they have shown that if there is a decomposition with ||s||_0 < (1+M^{-1})/2, where M denotes the coherence of the dictionary, this decomposition would be stable against noise. On the other hand, it is known that a sparse decomposition with ||s||_0 < spark(A)/2 is unique. In other words, although a decomposition with ||s||_0 < spark(A)/2 is unique, its stability against noise has been proved only for highly more restrictive decompositions satisfying ||s||_0 < (1+M^{-1})/2, because usually (1+M^{-1})/2 << spark(A)/2. This limitation maybe had not been very important before, because ||s||_0 < (1+M^{-1})/2 is also the bound which guaranties that the sparse decomposition can be found via minimizing the L1 norm, a classic approach for sparse decomposition. However, with the availability of new algorithms for sparse decomposition, namely SL0 and Robust-SL0, it would be important to know whether or not unique sparse decompositions with (1+M^{-1})/2 < ||s||_0 < spark(A)/2 are stable. In this paper, we show that such decompositions are indeed stable. In other words, we extend the stability bound from ||s||_0 < (1+M^{-1})/2 to the whole uniqueness range ||s||_0 < spark(A)/2. In summary, we show that all unique sparse decompositions are stably recoverable. Moreover, we see that sparser decompositions are more stable.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
