This paper studies the generalization capability of the compressed $k$-nearest neighbor (KNN) estimator, where randomly-projected low-dimensional data are put into the KNN estimator rather than the high-dimensional raw data. Considering both regression and classification, we give improved bounds on its generalization errors, to put more specific, $\ell_2$ error for regression and mis-classification rate for classification. As a byproduct of our analysis, we prove that ordered distance is almost preserved with random projections, which we believe is for the first time. In addition, we provide numerical experiments on various public datasets to verify our theorems.

This paper considers the unlabeled sparse recovery under multiple measurements, i.e., ${\mathbf{Y}} = {\mathbf{\Pi}}^{\natural} {\mathbf{X}} {\mathbf{B}}^{\natural} + {\mathbf{W}}$, where ${\mathbf{Y}} \in \mathbb{R}^{n\times m}, {\mathbf{\Pi}}^{\natural}\in \mathbb{R}^{n\times n}, {\mathbf{X}} \in \mathbb{R}^{n\times p}, {\mathbf{B}} ^{\natural}\in \mathbb{R}^{p\times m}, {\mathbf{W}}\in \mathbb{R}^{n\times m}$ represents the observations, missing (or incomplete) correspondence information, sensing matrix, sparse signals, and additive sensing noise, respectively. Different from the previous works on multiple measurements ($m > 1$) which all focus on the sufficient samples regime, namely, $n > p$, we consider a sparse matrix $\mathbf{B}^{\natural}$ and investigate the insufficient samples regime (i.e., $n \ll p$) for the first time. To begin with, we establish the lower bound on the sample number and signal-to-noise ratio ($ {\mathsf{SNR}}$) for the correct permutation recovery. Moreover, we present a simple yet effective estimator. Under mild conditions, we show that our estimator can restore the correct correspondence information with high probability. Numerical experiments are presented to corroborate our theoretical claims.

We consider the unlabeled linear regression reading as $\mathbf{Y} = \mathbf{\Pi}^{*}\mathbf{X}\mathbf{B}^* + \mathbf{W}$, where $\mathbf{\Pi}^{*}, \mathbf{B}^*$ and $\mathbf{W}$ represents missing (or incomplete) correspondence information, signals, and additive noise, respectively. Our goal is to perform data alignment between $\mathbf{Y}$ and $\mathbf{X}$, or equivalently, reconstruct the correspondence information encoded by $\mathbf{\Pi}^*$. Based on whether signal $\mathbf{B}^*$ is given a prior, we separately propose two greedy-selection-based estimators, which both reach the mini-max optimality. Compared with previous works, our work $(i)$ supports partial recovery of the correspondence information; and $(ii)$ applies to a general matrix family rather than the permutation matrices, to put more specifically, selection matrices, where multiple rows of $\mathbf{X}$ can correspond to the same row in $\mathbf{Y}$. Moreover, numerical experiments are provided to corroborate our claims.

In “Unlabeled Sensing”, one observes a set of linear measurements of an underlying signal with incomplete or missing information about their ordering, which can be modeled in terms of an unknown permutation. Previous work on the case of a single noisy measurement vector has exposed two main challenges: 1) a high requirement concerning thesignal-to-noise ratio($\mathsf {\mathbf {snr}}$), i.e., approximately of the order of$n^{5}$, and 2) a massive computational burden in light of NP-hardness in general. In this paper, we study the case ofmultiplenoisy measurement vectors (MMVs) resulting from acommonpermutation and investigate to what extent the number of MMVs$m$facilitates permutation recovery by “borrowing strength”. The above two challenges have at least partially been resolved within our work. First, we show that a large stable rank of the signal significantly reduces the required snr which can drop from a polynomial in$n$for$m = 1$to a constant for$m = \Omega (\log n)$, where$m$denotes the number of MMVs and$n$denotes the number of measurements per MV. This bound is shown to be sharp and is associated with a phase transition phenomenon. Second, we propose computational methods for recovering the unknown permutation. For the “oracle case” with known signal, the maximum likelihood (ML) estimator reduces to a linear assignment problem whose global optimum can be obtained efficiently. If both the signal and the permutation are unknown, the problem becomes a quadratic assignment problem; while such a problem is generally NP-hard and hence poses a significant challenge, we propose to tackle it via projected gradient descent with a non-convex constraint set, and establish a monotonic descent property of this scheme. Numerical experiments based on the proposed computational approach confirm the tightness of our theoretical analysis.

This paper considers the sparse recovery with ner-muted labels, i.e.,$\boldsymbol{y}={\Pi}^{\ast}\boldsymbol{X}{\beta}^{\ast}+\boldsymbol{w}$where$\boldsymbol{y} \in \mathbb{R}^{n}, \mathbf{\Pi} \in \mathbb{R}^{n \times n}, \boldsymbol{X} \in \mathbb{R}^{n \times p}, {\beta}^{\ast} \in \mathbb{R}^{p}, \boldsymbol{w} \in \mathbb{R}^{n}$denote the sensing result, unknown permutation matrix, design matrix, k-sparse covariates, and additive noise, respectively. The investigation is performed from both the statistical and the computational perspectives. For the statistical aspect, we first establish the statistical lower bounds on the measurement number$n$and the signal-to-noise ratio (SNR) for the correct recovery of the permutation matrix and the support set$\text{supp}({\beta}^{\ast})$, more specifically$n \gtrsim k \log p$and$\log (\text{SNR}) \gtrsim \log n+\frac{k \log p}{n}$. Then we confirm the tightness of these bounds by giving an exhaustive-search based estimators with matching orders. For the computational aspect, we propose a computationally-efficient estimator, namely, M-Lasso to recover both the permutation matrix and the sparse covariates. Numerical experiments are provided to verify the correctness and efficiency of the proposed estimator.

This paper proposes a general framework to design a sparse sensing matrix ${\mathbf {A}} \in \mathbb{R}^{m\times n}$, in a linear measurement system ${\mathbf {y = Ax}}^{\sharp } + {\mathbf {w}}$, where ${\mathbf {y}} \in \mathbb{R}^{n}, {\mathbf {x}}^{\sharp } \in \mathbb{R}^{n}$, and w denote the measurements, the signal with certain structures, and the measurement noise, respectively. By viewing the signal reconstruction from the measurements as a message passing algorithm over a graphical model, we leverage tools from coding theory in the design of low density parity check codes, namely the density evolution, and provide a framework for the design of matrix A. Particularly, compared to the previous methods, our proposed framework enjoys the following desirable properties: (i) Universality: the design supports both regular sensing and preferential sensing, and incorporates them in a single frame-work; (ii) Flexibility: the framework can easily adapt the design of A to a signal $x^{\sharp }$ with different underlying structures. As an illustration, we consider the $\ell_{1}$ regularizer, which correspond to Lasso, for both the regular sensing and preferential sensing scheme. Noteworthy, our framework can reproduce the classical result of Lasso, i.e., $m \geq c_{0}k\log (n/k)$ (the regular sensing) with regular design after proper distribution approximation, where $c_{0}\gt 0$ is some fixed constant. We also provide numerical experiments to confirm the analytical results and demonstrate the superiority of our framework whenever a preferential treatment of a sub-block of vector $x^{\sharp }$ is required.

Unlabeled linear regression, or “linear regression with an unknown permutation”, has attracted increasing attentions due to its applications in (e.g.,) linkage record and de-anonymization. However, the computation of unlabeled linear regression proves to be cumbersome and existing algorithms typically require considerable time, especially in the high dimensional regime. In this paper, we propose a one-step estimator which is optimal from both the computational and the statistical aspects. From the computational perspective, our estimator exhibits the same order of computational complexity as that of the oracle case (which means the regression coefficients are known in advance and only the permutation needs recovery). From the statistical perspective, when comparing with the necessary conditions for permutation recovery, our requirement on the \emph{signal-to-noise ratio} ($\mathsf{SNR}$) agrees up to merely $\Omega\left(\log \log n\right)$ difference when the stable rank of the regression coefficients $\ensuremath{\mathbf{B}}^{\natural}$ is much less than $\log n/\log \log n$.

Performance of the reconstruction algorithms in compressed sensing largely depends on the characteristics of measurement matrices. As such, the construction and analysis of the measurement matrix is of paramount interest. In this paper, for the first time, we focus on the class of sparse sensing matrices with (non-negative) integer entries. This problem, among other applications, is particularly motivated by the constraint of measuring gene regulatory expressions. We study randomly generated matrices from the integer family and analyze their properties in terms of the covariance and RIP constant. We derive bounds for the coherence and RIP constant of such measurement matrices. Further, apart from the coherence, we find that the RIP constant is closely related to the minimum non-diagonal entry ρnin the covariance matrix, which is rarely studied before.

In this paper, we study a general framework for compressive sensing assuming the existence of the prior knowledge that x* belongs to the union of multiple convex sets, x* ε υi ℒi. In fact, by proper choices of these convex sets in the above framework, the problem can be transformed to well known CS problems such as the phase retrieval, quantized compressive sensing, and model-based CS. First we analyze the impact of this prior knowledge on the minimum number of measurements M to guarantee the uniqueness of the solution. Then we formulate a universal objective function for signal recovery, which is both computationally inexpensive and flexible. Then, an algorithm based on multiplicative weight update and proximal gradient descent is proposed and analyzed for signal reconstruction. Finally, we investigate as to how we can improve the signal recovery by introducing regularizers into the objective function.

In Unlabeled Sensing, one observes a set of linear measurements of an underlying signal with incomplete or missing information about their ordering, which can be modeled in terms of an unknown permutation. In this paper, we study the case of multiple noisy measurement vectors (MMVs) resulting from a common permutation and investigate to what extent the number of MMVs m facilitates permutation recovery by "borrowing strength". We provide an affirmative answer for an oracle setting in which the matrix of signals is known by establishing matching upper and lower bounds on the required Signal-to-Noise Ratio (SNR), which – as distinguished from the case of a single measurement vector – involves a dependence on the stable rank of the matrix of signals. Specifically, a larger stable rank significantly reduces the required average SNR which can drop from nΩ(1)for m = 1 to Ω(log n) for m = Ω(log n), where n denotes the number of measurements per MMV. Numerical results are well-aligned with our theoretical findings.

In general, uncertainties in the sensing matrix weakens the system performance and reduces the reliability of recovered signals. In some applications, the sign values of signals instead of their exact values may be needed. In this paper, we show that as long as the uncertainty in the sensing matrix is sparse, a thresholding mechanism can be developed to recover the sign vector. In particular, provided that the true signal satisfies certain conditions, the exact sign vector can be recovered with high probability even under uncertain sensing matrices. Simulations are also presented to verify our theoretical results.

In certain applications, recovering the signs of values may be more critical than the values themselves. Inspired by advances of sparse recovery of signals with fewer measurements, we would like to study the sign recovery problem and generalize it from a linear case to a non-linear setup. We focus on the sign values in quadratic measurement systems and provide theorems for the consistency condition, which ensures the signs are recovered correctly with probability close to 1. In deriving the consistency condition, we adopt a new penalty term using the trace operation and transform the optimization problem to the widely known Lasso problem. We also present simulation results to verify the correctness of our theorems.

In many sparse sensing applications, it is desirable to limit not only the number of non-zero variables but also the amplitude or energy of the signal, i.e., the non-zero variables are expected to be in a certain range. One approach to incorporate the energy constraint is using objective functions such as IIxII22+ λ||χ||ο In this paper, we consider minimizing this objective function, given the linear sensing system y = Ax. As this optimization problem is not convex, we first find the convex envelope of the objective function and then analyze the relation between the uniqueness of the solution and the required number of sensors. Further, we show that the sparsity of the measurement matrix A has negative effects on the required number of sensors.

In a cognitive radio (CR) network, the transmitting signal of a secondary user (SU) is traditionally considered to be harmful for the primary user (PU), since it decreases the capacity of the PU's channel. However, for PU's secrecy capacity, the SUs' interference can be beneficial if it decreases the capacity of the source-eavesdropper channel more than that of the source-destination channel. In this paper, we consider using the SUs' interference to improve the PU's secrecy capacity and providing the SUs the opportunity to access the spectrum as a reward. But, there exists a tradeoff between the SUs' channel capacity and the PU's secrecy capacity. To decide which SUs can share the spectrum with the PU, we present a coalition formation game model with nontransferable utility, and propose a merge and split algorithm. The simulation results verify the efficiency of the proposed algorithm in terms of both the SUs' channel capacity and the PU's secrecy capacity in various scenarios.

Device-to-Device (D2D) communications have been proposed recently to improve the spectral efficiency. In this paper, we consider physical-layer security in D2D communication as an underlay to cellular networks with an eavesdropper. Benefiting from the underlaid spectrum reuse, D2D users can contribute to the system secrecy capacity, while D2D users may interfere the cellular users and decrease their secrecy capacity. We formulate this problem as a matching problem in the weighted bipartite graph and introduce the Kuhn-Munkres (KM) algorithm to provide the optimal solution. Simulation results show that the system secrecy capacity can be greatly improved by introducing D2D communications underlaying cellular networks.