Search

Let $\mathrm {W}\in \mathbb {C}^{n\times n}$ be a single-spiked Wishart matrix in the class $\mathrm {W}\sim \mathcal {CW}_{n}(m,\mathrm {I}_{n}+ \theta \mathrm {v}\mathrm {v}^{\dagger}) $ with $m\geq n$ , where ${\mathrm {I}}_{n}$ is the $n\times n$ identity matrix, $\mathrm {v}\in \mathbb {C}^{n\times 1}$ is an arbitrary vector with unit Euclidean norm, $\theta \geq 0$ is a non-random parameter, and $(\cdot)^{\dagger} $ represents the conjugate-transpose operator. Let u1 and ${\mathrm {u}}_{n}$ denote the eigenvectors corresponding to the smallest and the largest eigenvalues of W, respectively. This paper investigates the probability density function (p.d.f.) of the random quantity $Z_{\ell }^{(n)}=\left |{\mathrm {v}^{\dagger} \mathrm {u}_\ell }\right |^{2}\in (0,1)$ for $\ell =1,n$. In particular, we derive a finite dimensional closed-form p.d.f. for $Z_{1}^{(n)}$ which is amenable to asymptotic analysis as $m,n$ diverges with $m-n$ fixed. It turns out that, in this asymptotic regime, the scaled random variable $nZ_{1}^{(n)}$ converges in distribution to $\chi ^{2}_{2}/2(1+\theta)$ , where $\chi _{2}^{2}$ denotes a chi-squared random variable with two degrees of freedom. This reveals that u1 can be used to infer information about the spike. On the other hand, the finite dimensional p.d.f. of $Z_{n}^{(n)}$ is expressed as a double integral in which the integrand contains a determinant of a square matrix of dimension $(n-2)$. Although a simple solution to this double integral seems intractable, for special configurations of $n=2,3$ , and 4, we obtain closed-form expressions. [ABSTRACT FROM AUTHOR]

This paper considers the problem of secure parameter estimation when an estimation algorithm is prone to causative attacks. Causative attacks, in general, target decision-making algorithms (e.g., inference or learning algorithm) to alter their decisions in specific scenarios (e.g., distort parameter estimates for specific ranges of the parameter of interest). Such attacks influence the decisions via tampering with the mechanisms through which an algorithm acquires the statistical model of the population about which it aims to form a decision. Such attacks are viable, for instance, by contaminating the historical or training data, or by compromising an expert who provides the statistical model. In the presence of causative attacks, inference algorithms operate under a distorted statistical model for the data samples. This paper introduces a notion of secure parameter estimation and formalizes a framework under which secure estimation can be formulated and analyzed. The central premise underlying the secure estimation framework is that forming secure estimates introduces a new dimension to the estimation objective, pertaining to detecting attacks and isolating the true model. Since detection and isolation decisions themselves are imperfect, their inclusion induces an inherent coupling between the desired secure estimation objective and the auxiliary detection and isolation decisions that need to be formed in conjunction with the estimates. This paper establishes the fundamental interplay among these decisions, and characterizes the general decision rules in closed-forms for any desired estimation cost function. Furthermore, to circumvent the computational complexity associated with growing parameter dimension or attack complexity, a scalable estimation algorithm is provided, which is shown to enjoy certain optimality guarantees. Finally, the theory developed is applied to secure parameter estimation in sensor networks. [ABSTRACT FROM AUTHOR]

The main goal in group testing is to recover a small subset of defective items from a larger population while efficiently reducing the total number of (possibly noisy) required tests/measurements. Under the assumption that the input-output statistical relationship (i.e., channel law) is known to the recovery algorithm, the fundamental as well as the computational limits of the group testing problem are relatively better understood than when these statistical relationships are unknown. Practical considerations, however, render this assumption inapplicable, and “blind” recovery/estimation procedures, independent of the input-output statistics, are desired. In this paper, we analyze the fundamental limits of a general noisy group testing problem, when this relationship is unknown. Specifically, in the first part of this paper, we propose an efficient scheme, based on the idea of separate-decoding of items (where each item is recovered separately), for which we derive sufficient conditions on the number of tests required for exact recovery. The difficulty in obtaining these conditions stems from the fact that we allow the number of defective items to grow with the population size, which in turn requires delicate concentration analysis of certain probabilities. Furthermore, we show that in several scenarios, our proposed scheme achieves the same performance as that of the corresponding non-blind recovery algorithm (where the input-output statistics are known), implying that the proposed blind scheme is robust/universal. Finally, in the second part of this paper, we propose also an inefficient combinatorial-based scheme (or, “joint-decoding”), for which we derive similar sufficient conditions. [ABSTRACT FROM AUTHOR]

The basic goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. The outcome of a test on a subset of items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell $ defective items, where $0 \leq \ell < u$ , and arbitrary otherwise. This is called threshold group testing. The parameter $g = u - \ell - 1$ is called the gap. In this paper, we focus on the case $g > 0$ , i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case $g = 0$ ; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. Specifically, we present a better exact upper bound on the number of tests for disjunct matrices compared with that in related work. The third and fourth contributions are a reduced exact upper bound on the number of tests and a reduced asymptotic bound on the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems. [ABSTRACT FROM AUTHOR]

Sparse principal component analysis has become one of the most widely used techniques for dimensionality reduction in high-dimensional datasets. While many methods are available for point estimation of eigenstructure in high-dimensional settings, in this paper we propose methodology for uncertainty quantification, such as construction of confidence intervals and tests for the principal eigenvector and the corresponding largest eigenvalue. We base our methodology on an M-estimator with Lasso penalty which achieves minimax optimal rates and is used to construct a de-biased sparse PCA estimator. The novel estimator has a Gaussian limiting distribution and can be used for hypothesis testing or support recovery of the first eigenvector. The empirical performance of the new estimator is demonstrated on synthetic data and we also show that the estimator compares favourably with the classical PCA in moderately high-dimensional regimes. [ABSTRACT FROM AUTHOR]

This paper derives consistency results for estimation in the finite direct sum of reproducing kernel Hilbert spaces (RKHS) for dependent data. The link between penalized and constrained estimation is established. We consider the relation between topological equivalent norms for direct sums of RKHS. These norms have different implications for estimation. Estimation in a ball of the RKHS defined by these norms essentially results in estimation with a ridge and Lasso penalty, respectively. A greedy algorithm for the solution of the estimation problem under these two norms is discussed for general loss functions. [ABSTRACT FROM AUTHOR]

The objective of a genome-wide association study (GWAS) is to associate subsequences of individuals’ genomes to the observable characteristics called phenotypes (e.g., high blood pressure). Motivated by the GWAS problem, in this paper we introduce the information-theoretic problem of associated subsequence retrieval, where a dataset of N (possibly high-dimensional) sequences of length G, and their corresponding observable (binary) characteristics is given. The sequences are chosen independently and uniformly at random from $\mathcal {X}^{\text {G}}$ , where $\mathcal {X}$ is a finite alphabet. The observable (binary) characteristic is only related to a specific unknown subsequence of length $L$ of the sequences, called associated subsequence. For each sequence, if the associated subsequence of it belongs to a universal finite set, then it is more likely to display the observable characteristic (i.e., it is more likely that the observable characteristic is one). The goal is to retrieve the associated subsequence using a dataset of N sequences and their observable characteristics. We demonstrate that as the parameters N, G, and L grow, a threshold effect appears in the curve of probability of error versus the rate which is defined as ${{\it\text { Gh}}(\text {L}/\text {G})}/{\text {N}}$ , where $\text {h}(\cdot)$ is the binary entropy function. This effect allows us to define the capacity of associated subsequence retrieval. We develop an achievable scheme and a matching converse for this problem, and thus characterize its capacity in two scenarios: the zero-error-rate and the $\epsilon $ -error-rate. [ABSTRACT FROM AUTHOR]

Early stopping of iterative algorithms is a widely used form of regularization in statistics, commonly used in conjunction with boosting and related gradient-type algorithms. Although consistency results have been established in some settings, such estimators are less well-understood than their analogues based on penalized regularization. In this paper, for a relatively broad class of loss functions and boosting algorithms (including $L^{2}$ -boost, LogitBoost, and AdaBoost, among others), we exhibit a direct connection between the performance of a stopped iterate and the localized Gaussian complexity of the associated function class. This connection allows us to show that the local fixed point analysis of Gaussian or Rademacher complexities, now standard in the analysis of penalized estimators, can be used to derive optimal stopping rules. We derive such stopping rules in detail for various kernel classes and illustrate the correspondence of our theory with practice for Sobolev kernel classes. [ABSTRACT FROM AUTHOR]

In group testing, simple binary-output tests are designed to identify a small number $t$ of defective items that are present in a large population of $N$ items. Each test takes as input a group of items and produces a binary output indicating whether the group is free of the defective items or contains one or more of them. In this paper, we study a relaxation of the combinatorial group testing problem. A matrix is called $(t,\epsilon )$ -disjunct if it gives rise to a nonadaptive group testing scheme with the property of identifying a uniformly random $t$ -set of defective subjects out of a population of size $N$ with false positive probability of an item at most $\epsilon $ . We establish a new connection between $(t,\epsilon )$ -disjunct matrices and error correcting codes based on the dual distance of the codes and derive estimates of the parameters of codes that give rise to such schemes. Our methods rely on the moments of the distance distribution of codes and inequalities for moments of sums of independent random variables. We also provide a new connection between group testing schemes and combinatorial designs. [ABSTRACT FROM PUBLISHER]

In the classical non-adaptive group testing setup, pools of items are tested together, and the main goal of a recovery algorithm is to identify the complete defective set given the outcomes of different group tests. In contrast, the main goal of a non-defective subset recovery algorithm is to identify a subset of non-defective items given the test outcomes. In this paper, we present a suite of computationally efficient and analytically tractable non-defective subset recovery algorithms. By analyzing the probability of error of the algorithms, we obtain bounds on the number of tests required for non-defective subset recovery with arbitrarily small probability of error. Our analysis accounts for the impact of both the additive noise (false positives) and dilution noise (false negatives). By comparing with information theoretic lower bounds, we show that the upper bounds on the number of tests are orderwise tight up to a \log ^2K factor, where $K$ is the number of defective items. We also provide simulation results that compare the relative performance of the different algorithms and reveal insights into their practical utility. The proposed algorithms significantly outperform the straightforward approaches of testing items one-by-one, and of first identifying the defective set and then choosing the non-defective items from the complement set, in terms of the number of measurements required to ensure a given success rate. [ABSTRACT FROM PUBLISHER]

Total Bregman divergences are a recent tweak of ordinary Bregman divergences originally motivated by applications that required invariance by rotations. They have displayed superior results compared with ordinary Bregman divergences on several clustering, computer vision, medical imaging, and machine learning tasks. These preliminary results raise two important problems. First, report a complete characterization of the left and right population minimizers for this class of total Bregman divergences. Second, characterize a principled superset of total and ordinary Bregman divergences with good clustering properties, from which one could tailor the choice of a divergence to a particular application. In this paper, we provide and study one such superset with interesting geometric features, that we call conformal divergences, and focus on their left and right population minimizers. Our results are obtained in a recently coined $(u, v)$ -geometric structure that is a generalization of the dually flat affine connections in information geometry. We characterize both analytically and geometrically the population minimizers. We prove that conformal divergences (resp. total Bregman divergences) are essentially exhaustive for their left (resp. right) population minimizers. We further report new results and extend previous results on the robustness to outliers of the left and right population minimizers, and discuss the role of the $(u, v)$ -geometric structure in clustering. Additional results are also given. [ABSTRACT FROM PUBLISHER]

This paper discovers fundamental principles of the backoff process that governs the performance of IEEE 802.11. A simplistic principle founded upon regular variation theory is that the backoff time has a truncated Pareto-type tail distribution with an exponent of (\log \gamma \!)/\log m ( \boldsymbol m is the multiplicative factor and \gamma is the collision probability). This reveals that the per-node backoff process is heavy-tailed in the strict sense for \gamma > 1/m^2 , and paves the way for the following unifying result. The state-of-the-art theory on the superposition of the heavy-tailed processes is applied to establish a dichotomy exhibited by the aggregate backoff process, putting emphasis on the importance of time-scales on which we view the backoff processes. While the aggregation on normal time-scales leads to a Poisson process, it is approximated by a new limiting process possessing long-range dependence (LRD) on coarse time-scales. This dichotomy turns out to be instrumental in formulating short-term fairness, extending existing formulas to arbitrary population, and to elucidate the absence of LRD in practical situations. A refined wavelet analysis is conducted to strengthen this argument. [ABSTRACT FROM AUTHOR]

We consider the high-dimensional discriminant analysis problem. For this problem, different methods have been proposed and justified by establishing exact convergence rates for the classification risk, as well as the \ell 2 convergence results to the discriminative rule. However, sharp theoretical analysis for the variable selection performance of these procedures have not been established, even though model interpretation is of fundamental importance in scientific data analysis. This paper bridges the gap by providing sharp sufficient conditions for consistent variable selection using the sparse discriminant analysis. Through careful analysis, we establish rates of convergence that are significantly faster than the best known results and admit an optimal scaling of the sample size $n$ , dimensionality $p$ , and sparsity level $s$ in the high-dimensional setting. Sufficient conditions are complemented by the necessary information theoretic limits on the variable selection problem in the context of high-dimensional discriminant analysis. Exploiting a numerical equivalence result, our method also establish the optimal results for the ROAD estimator and the sparse optimal scoring estimator. Furthermore, we analyze an exhaustive search procedure, whose performance serves as a benchmark, and show that it is variable selection consistent under weaker conditions. Extensive simulations demonstrating the sharpness of the bounds are also provided. [ABSTRACT FROM AUTHOR]

This paper studies the limiting behavior of a class of robust population covariance matrix estimators, originally due to Maronna in 1976, in the regime where both the number of available samples and the population size grow large. Using tools from random matrix theory, we prove that, for sample vectors made of independent entries having some moment conditions, the difference between the sample covariance matrix and (a scaled version of) such robust estimator tends to zero in spectral norm, almost surely. This result can be applied to various statistical methods arising from random matrix theory that can be made robust without altering their first order behavior. [ABSTRACT FROM PUBLISHER]

This paper studies the sample complexity of searching over multiple populations. We consider a large number of populations, each corresponding to either distribution P0 or P1. The goal of the search problem studied here is to find one population corresponding to distribution P1 with as few samples as possible. The main contribution is to quantify the number of samples needed to correctly find one such population. We consider two general approaches: nonadaptive sampling methods, which sample each population a predetermined number of times until a population following P1 is found, and adaptive sampling methods, which employ sequential sampling schemes for each population. We first derive a lower bound on the number of samples required by any sampling scheme. We then consider an adaptive procedure consisting of a series of sequential probability ratio tests, and show it comes within a constant factor of the lower bound. We give explicit expressions for this constant when samples of the populations follow Gaussian and Bernoulli distributions. An alternative adaptive scheme is discussed which does not require full knowledge of P1, and comes within a constant factor of the optimal scheme. For comparison, a lower bound on the sampling requirements of any nonadaptive scheme is presented. [ABSTRACT FROM AUTHOR]