On the Foundation of Sparse Sensing (Part II): Diophantine Sampling and Array Configuration

In the second part of the series papers, we set out to study the algorithmic efficiency of sparse sensing. Stemmed from co-prime sensing, we propose a generalized framework, termed Diophantine sensing, which utilizes generic Diophantine equation theory and higher-order sparse ruler to strengthen the sampling time, the degree of freedom (DoF), and the sampling sparsity, simultaneously. Resorting to higher-moment statistics, the proposed Diophantine framework presents two fundamental improvements. First, on frequency estimation, we prove that given arbitrarily large down-sampling rates, there exist sampling schemes where the number of samples needed is only proportional to the sum of DoF and the number of snapshots required, which implies a linear sampling time. Second, on Direction-of-arrival (DoA) estimation, we propose two generic array constructions such that given N sensors, the minimal distance between sensors can be as large as a polynomial of N, O(N^q), which indicates that an arbitrarily sparse array (with arbitrarily small mutual coupling) exists given sufficiently many sensors. In addition, asymptotically, the proposed array configurations produce the best known DoF bound compared to existing sparse array designs.

On the Foundation of Sparse Sensing (Part I): Necessary and Sufficient Sampling Theory and Robust Remaindering Problem

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.

Statistical Robust Chinese Remainder Theorem for Multiple Numbers

Generalized Chinese Remainder Theorem (CRT) is a well-known approach to solve ambiguity resolution related problems. In this paper, we study the robust CRT reconstruction for multiple numbers from a view of statistics. To the best of our knowledge, it is the first rigorous analysis on the underlying statistical model of CRT-based multiple parameter estimation. To address the problem, two novel approaches are established. One is to directly calculate a conditional maximum a posteriori probability (MAP) estimation of the residue clustering, and the other is based on a generalized wrapped Gaussian mixture model to iteratively search for MAP of both estimands and clustering. Residue error correcting codes are introduced to improve the robustness further. Experimental results show that the statistical schemes achieve much stronger robustness compared to state-of-the-art deterministic schemes, especially in heavy-noise scenarios.

From Co-prime to the Diophantine Equation Based Sparse Sensing

With a careful design of sample spacings either in temporal and spatial domain, co-prime sensing can reconstruct the autocorrelation at a significantly denser set of points based on Bazout theorem. However, still restricted from Bazout theorem, it is required O(M1 + M2) samples to estimate frequencies in the case of co-prime sampling, where M1 and M2 are co-prime down-sampling rates. Besides, for Direction-of-arrival (DOA) estimation, the sensors can not be arbitrarily sparse in co-prime arrays. In this letter, we restrain our focus on complex waveforms and present a framework under multiple samplers/sensors for both frequency and DOA estimation based on Diophantine equation, which is essentially to estimate the autocorrelation with higher order statistics instead of the second order one. We prove that, given arbitrarily high down-sampling rates, there exist sampling schemes with samples to estimate autocorrelation only proportional to the sum of degrees of freedom (DOF) and the number of snapshots required. In the scenario of DOA estimation, we show there exist arrays of N sensors with O(N^3) DOF and O(N) minimal distance between sensors.

Local Differential Privacy in Decentralized Optimization

Privacy concerns with sensitive data are receiving increasing attention. In this paper, we study local differential privacy (LDP) in interactive decentralized optimization. By constructing random local aggregators, we propose a framework to amplify LDP by a constant. We take Alternating Direction Method of Multipliers (ADMM), and decentralized gradient descent as two concrete examples, where experiments support our theory. In an asymptotic view, we address the following question: Under LDP, is it possible to design a distributed private minimizer for arbitrary closed convex constraints with utility loss not explicitly dependent on dimensionality? As an affiliated result, we also show that with merely linear secret sharing, information theoretic privacy is achievable for bounded colluding agents.

Statistical Robust Chinese Remainder Theorem for Multiple Numbers: Wrapped Gaussian Mixture Model

Generalized Chinese Remainder Theorem (CRT) has been shown to be a powerful approach to solve the ambiguity resolution problem. However, with its close relationship to number theory, study in this area is mainly from a coding theory perspective under deterministic conditions. Nevertheless, it can be proved that even with the best deterministic condition known, the probability of success in robust reconstruction degrades exponentially as the number of estimand increases. In this paper, we present the first rigorous analysis on the underlying statistical model of CRT-based multiple parameter estimation, where a generalized Gaussian mixture with background knowledge on samplings is proposed. To address the problem, two novel approaches are introduced. One is to directly calculate the conditional maximal a posteriori probability (MAP) estimation of residue clustering, and the other is to iteratively search for MAP of both common residues and clustering. Moreover, remainder error-correcting codes are introduced to improve the robustness further. It is shown that this statistically based scheme achieves much stronger robustness compared to state-of-the-art deterministic schemes, especially in low and median Signal Noise Ratio (SNR) scenarios.

On Solving Ambiguity Resolution with Robust Chinese Remainder Theorem for Multiple Numbers

Chinese Remainder Theorem (CRT) is a powerful approach to solve ambiguity resolution related problems such as undersampling frequency estimation and phase unwrapping which are widely applied in localization. Recently, the deterministic robust CRT for multiple numbers (RCRTMN) was proposed, which can reconstruct multiple integers with unknown relationship of residue correspondence via generalized CRT and achieves robustness to bounded errors simultaneously. Naturally, RCRTMN sheds light on CRT-based estimation for multiple objectives. In this paper, two open problems arising that how to introduce statistical methods into RCRTMN and deal with arbitrary errors introduced in residues are solved. We propose the extended version of RCRTMN assisted with Maximum Likelihood Estimation (MLE), which can tolerate unrestricted errors and bring considerable improvement in robustness.

Robustness in Chinese Remainder Theorem

Chinese Remainder Theorem (CRT) has been widely studied with its applications in frequency estimation, phase unwrapping, coding theory and distributed data storage. Since traditional CRT is greatly sensitive to the errors in residues due to noises, the problem of robustly reconstructing integers via the erroneous residues has been intensively studied in the literature. In order to robustly reconstruct integers, there are two kinds of traditional methods: the one is to introduce common divisors in the moduli and the other is to directly decrease the dynamic range. In this paper, we take further insight into the geometry property of the linear space associated with CRT. Echoing both ways to introduce redundancy, we propose a pseudo metric to analyze the trade-off between the error bound and the dynamic range for robust CRT in general. Furthermore, we present the first robust CRT for multiple numbers to solve the problem of the CRT-based undersampling frequency estimation in general cases. Based on symmetric polynomials, we proved that in most cases, the problem can be solved in polynomial time efficiently. The work in this paper is towards a complete theoretical solution to the open problem over 20 years.