Search

The conventional model of disjunctive group testing assumes that there are several defective elements (or defectives) among a large population, and a group test yields the positive response if and only if the testing group contains at least one defective element. The basic problem is to find all defectives using a minimal possible number of group tests. However, when the number of defectives is unknown there arises an additional problem, namely: how to estimate the random number of defective elements. In this paper, we concentrate on testing the hypothesis $H_0$ : the number of defectives $\leq s_1$ against the alternative hypothesis $H_1$ : the number of defectives $\geq s_2$. We introduce a new decoding algorithm based on the comparison of the number of tests having positive responses with an appropriate fixed threshold. For some asymptotic regimes on $s_1$ and $s_2$ , the proposed algorithm is shown to be order-optimal. Additionally, our simulation results verify the advantages of the proposed algorithm such as low complexity and a small error probability compared with known algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes a novel proximal-gradient algorithm for a decentralized optimization problem with a composite objective containing smooth and nonsmooth terms. Specifically, the smooth and nonsmooth terms are dealt with by gradient and proximal updates, respectively. The proposed algorithm is closely related to a previous algorithm, PG-EXTRA (W. Shi, Q. Ling, G. Wu, and W. Yin, “A proximal gradient algorithm for decentralized composite optimization,” IEEE Trans. Signal Process., vol. 63, no. 22, pp. 6013–6023, 2015), but has a few advantages. First of all, agents use uncoordinated step-sizes, and the stable upper bounds on step-sizes are independent of network topologies. The step-sizes depend on local objective functions, and they can be as large as those of the gradient descent. Second, for the special case without nonsmooth terms, linear convergence can be achieved under the strong convexity assumption. The dependence of the convergence rate on the objective functions and the network are separated, and the convergence rate of the new algorithm is as good as one of the two convergence rates that match the typical rates for the general gradient descent and the consensus averaging. We provide numerical experiments to demonstrate the efficacy of the introduced algorithm and validate our theoretical discoveries. [ABSTRACT FROM AUTHOR]

Due to the advantage of capacity-achieving, polar codes have been extended to the block fading channel whereas most constructions involve complex iterative-calculation. In this paper, we establish a systematic framework to analyze the error performance of polar codes in the case of block mapping and random mapping. For both the mappings, by introducing the new concept, named split polar spectrum, we derive the upper bound on the error probability of polarized channel which explicitly reveals the relationship between the diversity order $L$ and the block-wise weight distribution of the codeword. For the special case $L=2$ in the block mapping, we design the enumeration algorithm to calculate the exact split polar spectrum based on the general MacWilliams identities. For arbitrary diversity order in the random mapping, with the help of uniform interleaving, we derive the approximate split polar spectrum by combining the polar spectrum and the probability of fading pattern for a specific weight. Furthermore, we propose the design criteria to construct polar codes over the block fading channel. The full diversity criterion is the primary target to achieve the diversity gain and the product distance criterion requires to maximize the product of the block-wise Hamming distance whereby obtain the coding gain. Guided by these design criteria, the construction metrics, respectively named polarized diversity weight (PDW) and simplified PDW (SPDW) are proposed to designpolar codes in both mappings. Such simple metrics can construct polar codes with similar or better performance over those based on traditional methods in block fading channel. [ABSTRACT FROM AUTHOR]

This paper provides new probabilistic guarantees for recovering the common support of jointly sparse vectors in multiple measurement vector (MMV) models. In recent times, Bayesian approaches for sparse signal recovery (such as sparse Bayesian learning and correlation-aware LASSO) have shown preliminary evidence that under appropriate conditions (such as access to ideal covariance matrix of the measurements or certain restrictive orthogonality condition on the signals), it is possible to recover supports of size ($K$) larger than the dimension ($M$) of each measurement vector. However, no results exist that characterize the probability with which this can be achieved for a finite number of measurement vectors ($L$). This paper bridges this gap by formulating the support recovery problem in terms of a multiple hypothesis testing framework. Chernoff-type upper bounds on the probability of error are established, and new sufficient conditions are derived that guarantee its exponential decay with respect to $L$ even when $K=O(M^2)$. Our sufficient conditions are based on the properties of the so-called Khatri–Rao product of the measurement matrix and reveal the importance of a sampler design. Negative results are also established indicating that when $K$ exceeds a certain threshold (in terms of $M$), there will exist a class of measurement matrices for which any support recovery algorithm will fail. Using results from the geometric probability, we characterize the probability with which a randomly generated measurement matrix will belong to this class and show that this probability tends to 1 asymptotically in the size ($N$) of the sparse vectors. [ABSTRACT FROM AUTHOR]

In this paper, in order to improve the Student's t-matching accuracy, a novel Kullback-Leibler divergence (KLD) minimization-based matching method is firstly proposed by minimizing the upper bound of the KLD between the true Student's t-density and the approximate Student's t-density. To improve the Student's t-modelling accuracy, a novel KLD minimization-based adaptive method is then proposed to estimate the scale matrices of Student's t-distributions, in which the modified evidence lower bound is maximized. A novel KLD minimization-based adaptive Student's t-filter is derived via combining the proposed Student's t-matching technique and the adaptive method. A manoeuvring target tracking example is provided to demonstrate the effectiveness and potential of the proposed filter. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of universal best arm identification in multi-armed bandits, where the underlying setting can be either stochastic or adversarial and is not revealed to the forecaster a priori. We propose an algorithm, called S3-BA, that identifies the best arm without prior knowledge of the underlying setting. The key idea is to simultaneously explore the arms and learn the problem setting, and switch when adversarial is declared. We analyze the performance of the proposed algorithm for both stochastic and adversarial bandits. For stochastic bandit, we prove an upper bound on the error rate of S3-BA. For adversarial bandit, we show that the best arm can be guaranteed as long as the budget is above a threshold. Both results are comparable to the best known algorithms that are specifically designed for the corresponding settings. More importantly, we prove that the “learning loss” due to the formulation uncertainty is negligible compared to the arm selection policies, for both stochastic and adversarial bandits. We also propose an adaptive version of S3-BA, Ad-S3-BA, that facilitates the parameter tuning via a simultaneous gap estimation. Experimental results on both synthetic and real-world datasets corroborate the theoretical analysis of S3-BA, and in particular, demonstrate the performance superiority for the real-world datasets that exhibit a “pseudo-stochastic” behavior. [ABSTRACT FROM AUTHOR]

The paper addresses the transient change detection (TCD) problem, assuming that the duration of change is finite. The TCD criterion minimizes the worst-case probability of missed detection among all tests with a prescribed worst-case probability of false alarm. We study the fixed sample size (FSS) test as a solution to the TCD problem. First, the operating characteristics of the FSS test have been established for arbitrary pre- and post-change distributions. Next, a numerical method of the sample (block) size optimization has been considered for three particular log-likelihood ratio distributions, i.e., Gaussian, $\chi ^{2}$ and exponential. Moreover, simple asymptotic equations for the optimal operating characteristics and block size have been proposed in the Gaussian case. Numerical results are provided to confirm the theoretical findings for the above-mentioned distributions. The accuracy and sharpness of the asymptotic analytical equation is analyzed in the Gaussian case. Finally, the FSS test is compared to the finite moving average (FMA) test obtained by optimizing the CUSUM-type test with respect to the TCD optimality criterion for the above-mentioned distributions. The application of the FSS and FMA tests to the radio-navigation integrity monitoring is also considered. [ABSTRACT FROM AUTHOR]

A deep community in a graph is a connected component that can only be seen after removal of nodes or edges from the rest of the graph. This paper formulates the problem of detecting deep communities as multi-stage node removal that maximizes a new centrality measure, called the local Fiedler vector centrality (LFVC), at each stage. The LFVC is associated with the sensitivity of algebraic connectivity to node or edge removals. We prove that a greedy node/edge removal strategy, based on successive maximization of LFVC, has bounded performance loss relative to the optimal, but intractable, combinatorial batch removal strategy. Under a stochastic block model framework, we show that the greedy LFVC strategy can extract deep communities with probability one as the number of observations becomes large. We apply the greedy LFVC strategy to real-world social network datasets. Compared with conventional community detection methods we demonstrate improved ability to identify important communities and key members in the network. [ABSTRACT FROM PUBLISHER]

The fundamental problem of multiple secondary users contending for opportunistic spectrum access over multiple channels in cognitive radio networks has been formulated recently as a decentralized multi-armed bandit (D-MAB) problem. In a D-MAB problem there are M users and N arms (channels) that each offer i.i.d. stochastic rewards with unknown means so long as they are accessed without collision. The goal is to design distributed online learning policies that incur minimal regret. We consider two related problem formulations in this paper. First, we consider the setting where the users have a prioritized ranking, such that it is desired for the K-th-ranked user to learn to access the arm offering the K-th highest mean reward. For this problem, we present DLP, the first distributed policy that yields regret that is uniformly logarithmic over time without requiring any prior assumption about the mean rewards. Second, we consider the case when a fair access policy is required, i.e., it is desired for all users to experience the same mean reward. For this problem, we present DLF, a distributed policy that yields order-optimal regret scaling with respect to the number of users and arms, better than previously proposed policies in the literature. Both of our distributed policies make use of an innovative modification of the well-known UCB1 policy for the classic multi-armed bandit problem that allows a single user to learn how to play the arm that yields the KK-th largest mean reward. [ABSTRACT FROM AUTHOR]

We investigate the multiple-input multiple-output broadcast channel with statistical channel state information available at the transmitter. The so-called linear assignment operation is employed, and necessary conditions are derived for the optimal transmit design under general fading conditions. Based on this, we introduce an iterative algorithm to maximize the linear assignment weighted sum-rate by applying a gradient descent method. To reduce complexity, we derive an upper bound of the linear assignment achievable rate of each receiver, from which a simplified closed-form expression for a near-optimal linear assignment matrix is derived. This reveals an interesting construction analogous to that of dirty-paper coding. In light of this, a low-complexity transmission scheme is provided. Numerical examples illustrate the significant performance of the proposed low complexity scheme. [ABSTRACT FROM PUBLISHER]

This paper considers metric the exact dissimilarities between pairs of points are not unknown but known to belong to some interval. The goal is to study methods for the determination of hierarchical clusters, i.e., a family of nested partitions indexed by a resolution parameter, induced from the given distance intervals of the dissimilarities. Our construction of hierarchical clustering methods is based on defining admissible methods to be those methods that satisfy the axioms of value—nodes in a metric space with two nodes are clustered together at the convex combination of the upper and lower bounds determined by a parameter—and transformation—when both distance bounds are reduced, the output may become more clustered but not less. Two admissible methods are constructed and are shown to provide universal bounds in the space of admissible methods. Practical implications are explored by clustering moving points via snapshots and by clustering coauthorship networks representing collaboration between researchers from different communities. The proposed clustering methods succeed in identifying underlying hierarchical clustering structures via the maximum and minimum distances in all snapshots, as well as in differentiating collaboration patterns in journal publications between different research communities based on bounds of network distances. [ABSTRACT FROM AUTHOR]

The non-homogeneous Poisson process provides a generalised framework for the modelling of random point data by allowing the intensity of point generation to vary across its domain of interest (time or space). The use of non-homogeneous Poisson processes have arisen in many areas of signal processing and machine learning, but application is still largely limited by its intractable likelihood function and the lack of computationally efficient inference schemes, although some methods do exist for the batch data case. In this paper, we propose for the first time a sequential framework for intensity inference which combines the non-homogeneous model of Poisson data with continuous-time state-space models for their time-varying intensity. This approach enables us to design efficient online inference schemes, for which we propose a novel sequential Markov chain Monte Carlo (SMCMC) algorithm, as is demanded by many applications where point data arrive sequentially and decisions need to be made with low latency. The proposed approach is compared with competing methods on synthetic datasets and tested with high-frequency financial order book data, showing in general improved performance and better computational efficiency than the main batch-based competitor algorithm, and better performance than a simple baseline kernel estimation scheme. [ABSTRACT FROM AUTHOR]

In this paper, the joint support recovery of several sparse signals whose supports exhibit similarities is examined. Each sparse signal is acquired using the same noisy linear measurement process, which returns fewer observations than the dimension of the sparse signals. The measurement noise is assumed additive, Gaussian, and admits different variances for each sparse signal that is measured. Using the theory of compressed sensing, the performance of simultaneous orthogonal matching pursuit (SOMP) is analyzed for the envisioned signal model. The cornerstone of this paper is a novel analysis method upper bounding the probability that SOMP recovers at least one incorrect entry of the joint support during a prescribed number of iterations. Furthermore, the probability of SOMP failing is investigated whenever the number of sparse signals being recovered simultaneously increases and tends to infinity. In particular, convincing observations and theoretical results suggest that SOMP committing no mistake in the noiseless case does not guarantee the absence of error in the noisy case whenever the number of acquired sparse signals scales to infinity. Finally, simulation results confirm the validity of the theoretical results. [ABSTRACT FROM PUBLISHER]

This paper considers the classification of linear subspaces with mismatched classifiers. In particular, we assume a model where one observes signals in the presence of isotropic Gaussian noise and the distribution of the signals conditioned on a given class is Gaussian with a zero mean and a low-rank covariance matrix. We also assume that the classifier knows only a mismatched version of the parameters of input distribution in lieu of the true parameters. By constructing an asymptotic low-noise expansion of an upper bound to the error probability of such a mismatched classifier, we provide sufficient conditions for reliable classification in the low-noise regime that are able to sharply predict the absence of a classification error floor. Such conditions are a function of the geometry of the true signal distribution, the geometry of the mismatched signal distributions as well as the interplay between such geometries, namely, the principal angles and the overlap between the true and the mismatched signal subspaces. Numerical results demonstrate that our conditions for reliable classification can sharply predict the behavior of a mismatched classifier both with synthetic data and in a motion segmentation and a hand-written digit classification applications. [ABSTRACT FROM AUTHOR]

This paper studies clustering of data sequences using the k-medoids algorithm. All the data sequences are assumed to be generated from unknown continuous distributions, which form clusters with each cluster containing a composite set of closely located distributions (based on a certain distance metric between distributions). The maximum intracluster distance is assumed to be smaller than the minimum intercluster distance, and both values are assumed to be known. The goal is to group the data sequences together if their underlying generative distributions (which are unknown) belong to one cluster. Distribution distance metrics based k-medoids algorithms are proposed for known and unknown number of distribution clusters. Upper bounds on the error probability and convergence results in the large sample regime are also provided. It is shown that the error probability decays exponentially fast as the number of samples in each data sequence goes to infinity. The error exponent has a simple form regardless of the distance metric applied when certain conditions are satisfied. In particular, the error exponent is characterized when either the Kolmogrov–Smirnov distance or the maximum mean discrepancy are used as the distance metric. Simulation results are provided to validate the analysis. [ABSTRACT FROM AUTHOR]

Recovery of certain piecewise continuous signals from noisy observations has been a major challenge in sciences and engineering. In this paper, in a tight-dimensional representation space, we exploit sparsity hidden in a class of possibly discontinuous signals named finite-dimensional piecewise continuous (FPC) signals. More precisely, we propose a tight-dimensional linear transformation which reveals a certain sparsity in discrete samples of the FPC signals. This transformation is designed by exploiting the fact that most of the consecutive samples are contained in special subspaces. Numerical experiments on recovery of piecewise polynomial signals and piecewise sinusoidal signals show the effectiveness of the revealed sparsity. [ABSTRACT FROM AUTHOR]

In this paper, we derive mutual information based upper bounds on the number of nonadaptive group tests required to identify a given number of “non-defective” items from a large population containing a small number of “defective” items. In the asymptotic regime with the population size $N \rightarrow \infty$ , to identify $L$ nondefective items out of a population containing $K$ defective items, our results show that $\frac{C_s K}{1-o(1)} (\Phi (\alpha _0, \beta _0) + o(1))$ measurements are sufficient when the tests are reliable. Here, $C_s$ is a constant independent of $N, K$ , and $L$ , and $\Phi (\alpha _0, \beta _0)$ is a bounded function of $\alpha _0 \triangleq \lim _{N\rightarrow \infty } \frac{L}{N-K}$ and $\beta _0 \triangleq \lim _{N\rightarrow \infty } \frac{K}{N-K}$. In contrast, the necessary number of tests using the conventional approach of first identifying the $K$ defective items and picking the required number of nondefective items from the complement set grows with $N$ as $O\left(K \log N \right)$. We also derive upper bounds on the number of tests under both dilution and additive noise models. Our results are obtained under a very general sparse signal model, by virtue of which, they are also applicable to other important sparse signal based applications such as compressive sensing. [ABSTRACT FROM AUTHOR]

In sparse recovery, a sparse signal ${\mathbf x}\in \mathbb {R}^N$ with $K$ nonzero entries is to be reconstructed from a compressed measurement $\mathbf y=Ax$ with ${\mathbf A}\in \mathbb {R}^{M\times N}$ ($M

We show that the use of Schur complement lemma to derive equivalent convex constraints to those non-convex in (54) and (55) of the above paper is not valid. In this comment, an alternative approach is presented to convexify those constraints. [ABSTRACT FROM AUTHOR]

For an m x n binary matrix with d nonzero elements per column, it is interesting to identify the minimal column degree d that corresponds to the best recovery performance. Consider this problem is hard to be addressed with currently known performance parameters, we propose a new performance parameter, the average of nonzero correlations between normalized columns. The parameter is proved to perform better than the known coherence parameter, namely the maximum correlation between normalized columns, when used to estimate the performance of binary matrices with high compression ratios n/m and low column degrees d. By optimizing the proposed parameter, we derive an ideal column degree d = [√m 1, around which the best recovery performance is expected to be obtained. This is verified by simulations. Given the ideal number d of nonzero elements in each column, we further determine their specific distribution by minimizing the coherence with a greedy method. The resulting binary matrices achieve comparable or even better recovery performance than random binary matrices. [ABSTRACT FROM AUTHOR]

We are motivated by problems that arise in a number of applications such as Online Marketing and Explosives detection, where the observations are usually modeled using Poisson statistics. We model each observation as a Poisson random variable whose mean is a sparse linear superposition of known patterns. Unlike many conventional problems observations here are not identically distributed since they are associated with different sensing modalities. We analyze the performance of a maximum likelihood (ML) decoder, which for our Poisson setting involves a non-linear optimization but yet is computationally tractable. We derive fundamental sample complexity bounds for sparse recovery when the measurements are contaminated with Poisson noise. In contrast to the least-squares linear regression setting with Gaussian noise, we observe that in addition to sparsity, the scale of the parameters also fundamentally impacts \ell_2 error in the Poisson setting. We show that our upper bounds are tight under suitable regularity conditions. Specifically, we derive a minimax matching lower bound on the mean-squared error and show that our constrained ML decoder is minimax optimal for this regime. [ABSTRACT FROM AUTHOR]

In the problem of multiple support recovery, we are given access to linear measurements of multiple sparse samples in ${\mathbb {R}}^{d}$. These samples can be partitioned into $\ell$ groups, with samples having the same support belonging to the same group. For a given budget of $m$ measurements per sample, the goal is to recover the $\ell$ underlying supports, in the absence of the knowledge of group labels. We study this problem with a focus on the measurement-constrained regime where $m$ is smaller than the support size $k$ of each sample. We design a two-step procedure that estimates the union of the underlying supports first, and then uses a spectral algorithm to estimate the individual supports. Our proposed estimator can recover the supports with $m< k$ measurements per sample, from $\tilde{O}(k^{4}\ell ^{4}/m^{4})$ samples. Our guarantees hold for a general, generative model assumption on the samples and measurement matrices. We also provide results from experiments conducted on synthetic data and on the MNIST dataset. [ABSTRACT FROM AUTHOR]

We consider the problem of Bayesian optimization of a one-dimensional Brownian motion in which the $T$ adaptively chosen observations are corrupted by Gaussian noise. We show that the smallest possible expected cumulative regret and the smallest possible expected simple regret scale as $\Omega (\sigma \sqrt {T / \log (T)}) \cap \mathcal {O}(\sigma \sqrt {T} \cdot \log T)$ and $\Omega (\sigma / \sqrt {T \log (T)}) \cap \mathcal {O}(\sigma \log T / \sqrt {T})$ respectively, where $\sigma ^2$ is the noise variance. Thus, our upper and lower bounds are tight up to a factor of $\mathcal {O} ((\log T)^{1.5})$. The upper bound uses an algorithm based on confidence bounds and the Markov property of Brownian motion (among other useful properties), and the lower bound is based on a reduction to binary hypothesis testing. [ABSTRACT FROM AUTHOR]

For theessential set of discrete prolate spheroidal sequences (DPSS) corresponding to a given discrete-time-bandwidth product, we show that the auto and cross-correlations between the member sequences of the set also exhibit high concentration over a correlation length twice the concentration length of the member sequences. We start by deriving one upper bound and two lower bounds for the energy of the correlation sequence of index-limited DPSSs from which we derive similar bounds for the energy of DPSS correlation sequences. Then, we obtain an upper bound for the tail energy of DPSS correlation sequences. Finally, we obtain a lower bound for the concentration ratio of DPSS correlation sequences. All derived bounds require knowledge of the following parameters for each DPSS sequence in the correlation pair: corresponding eigen-value, Fourier transform evaluated at two special frequency points, derivative of the Fourier transform evaluated at the same two points. Most of the aforementioned parameters can be expressed or bounded by functions in the global parameters: sequence length and discrete-time-bandwidth. [ABSTRACT FROM AUTHOR]

Decentralized multi-agent optimization usually relies on information exchange between neighboring agents, which can incur unaffordable communication overhead in practice. To reduce the communication cost, we apply event-triggering technique to the decentralized multi-agent online convex optimization problem, where each agent is associated with a time-varying local loss function and the goal is to minimize the accumulated total loss (the sum of all local loss functions) by choosing appropriate actions sequentially. We first develop an event-triggered decentralized online subgradient descent algorithm for the full information case, where the local loss function is fully revealed to each agent at each time. We establish an upper bound for the regret of each agent in terms of the event-triggering thresholds. It is shown that the regret is sublinear provided that the event-triggering thresholds converge to zero as time goes to infinity. The algorithm and analysis are further extended to the scenario of bandit feedback, where only the values of the local loss function at two random points close to the current action are disclosed to each agent. We show that the two-point bandit feedback does not degrade the performance of the proposed algorithm in order sense and a regret bound similar to the full information case can be established. Finally, numerical results on the problem of decentralized online least squares are presented to validate the proposed algorithms. [ABSTRACT FROM AUTHOR]

We study conditions that allow accurate graphical model selection from non-stationary data. The observed data is modelled as a vector-valued zero-mean Gaussian random process whose samples are uncorrelated but have different covariance matrices. This model contains as special cases the standard setting of i.i.d. samples as well as the case of samples forming a stationary time series. More generally, our approach applies to any data for which efficient decorrelation transforms, such as the Fourier transform for stationary time series, are available. By analyzing a conceptually simple model selection method, we derive a sufficient condition on the required sample size for accurate graphical model selection based on non-stationary data. [ABSTRACT FROM AUTHOR]

We consider a variant of the classic multi-armed bandit problem where the expected reward of each arm is a function of an unknown parameter. The arms are divided into different groups, each of which has a common parameter. Therefore, when the player selects an arm at each time slot, information of other arms in the same group is also revealed. This regional bandit model naturally bridges the classical non-informative bandit setting where the player can only learn the chosen arm, and the global bandit model where sampling one arm reveals information of all arms. We propose an efficient algorithm, UCB-g, that solves the regional bandit model by combining the Upper Confidence Bound (UCB) and greedy principles. Both parameter-dependent and parameter-free regret upper bounds are derived. We also establish a matching lower bound, which proves the order optimality of UCB-g. Moreover, we propose SW-UCB-g, which is an extension of UCB-g for a non-stationary environment where the parameters vary over time. [ABSTRACT FROM AUTHOR]

We propose a geometric assumption on nonnegative data matrices such that under this assumption, we are able to provide upper bounds (both deterministic and probabilistic) on the relative error of nonnegative matrix factorization (NMF). The algorithm we propose first uses the geometric assumption to obtain an exact clustering of the columns of the data matrix; subsequently, it employs several rank-one NMFs to obtain the final decomposition. When applied to data matrices generated from our statistical model, we observe that our proposed algorithm produces factor matrices with comparable relative errors vis-à-vis classical NMF algorithms but with much faster speeds. On face image and hyperspectral imaging datasets, we demonstrate that our algorithm provides an excellent initialization for applying other NMF algorithms at a low computational cost. Finally, we show on face and text datasets that the combinations of our algorithm and several classical NMF algorithms outperform other algorithms in terms of clustering performance. [ABSTRACT FROM PUBLISHER]