Search

This paper considers a massive random access problem in which a large number of sporadically active devices wish to communicate with a base station (BS) equipped with massive multiple-input multiple-output (MIMO) antennas. Each device is preassigned a unique signature sequence, and the BS identifies the active devices by detecting which sequences are transmitted. This device activity detection problem can be formulated as a maximum likelihood estimation (MLE) problem for which the sample covariance matrix of the received signal is a sufficient statistic. The goal of this paper is to characterize the feasible set of problem parameters under which this covariance based approach is able to successfully recover the device activities in the massive MIMO regime. Through an analysis of the asymptotic behaviors of MLE via its associated Fisher information matrix, this paper derives a necessary and sufficient condition on the Fisher information matrix to ensure a vanishing probability of detection error as the number of antennas goes to infinity, based on which a numerical phase transition analysis is obtained. This condition is also examined from a perspective of covariance matching, which relates the phase transition analysis to a recently derived scaling law. Further, we provide a characterization of the distribution of the estimation error in MLE, based on which the error probabilities in device activity detection can be accurately predicted. Finally, this paper studies a random access scheme with joint device activity and data detection and analyzes its performance in a similar way. [ABSTRACT FROM AUTHOR]

Speckle or multiplicative noise is a critical issue in coherence-based imaging systems, such as synthetic aperture radar and optical coherence tomography. Existence of speckle noise considerably limits the applicability of such systems by degrading their performance. On the other hand, the sophistications that arise in the study of multiplicative noise have so far impeded theoretical analysis of such imaging systems. As a result, the current acquisition technology relies on heuristic solutions, such as oversampling the signal and converting the problem into a denoising problem with multiplicative noise. This paper attempts to bridge the gap between theory and practice by providing the first theoretical analysis of such systems. To achieve this goal the log-likelihood function corresponding to measurement systems with speckle noise is characterized. Then employing compression codes to model the source structure, for the case of under-sampled measurements, a compression-based maximum likelihood recovery method is proposed. The mean squared error (MSE) performance of the proposed method is characterized and is shown to scale as $O\left({\sqrt {\frac{k \log n }{ m}}}\right)$ , where $k$ , $m$ and $n$ denote the intrinsic dimension of the signal class according to the compression code, the number of observations, and the ambient dimension of the signal, respectively. This result, while in contrast to imaging systems with additive noise in which MSE scales as $O\left({{\frac{k \log n }{ m}}}\right)$ , suggests that if the signal class is structured (i.e., $k \ll n$), accurate recovery of a signal from under-determined measurements is still feasible, even in the presence of speckle noise. Simulation results are presented that suggest image recovery under multiplicative noise is inherently more challenging than additive noise, and that the derived theoretical results are sharp. [ABSTRACT FROM AUTHOR]

We consider the fundamental problem of matching a template to a signal. We do so by M-estimation, which encompasses procedures that are robust to gross errors (i.e., outliers). Using standard results from empirical process theory, we derive the convergence rate and the asymptotic distribution of the M-estimator under relatively mild assumptions. We also discuss the optimality of the estimator, both in finite samples in the minimax sense and in the large-sample limit in terms of local minimaxity and relative efficiency. Although most of the paper is dedicated to the study of the basic shift model in the context of a random design, we consider many extensions towards the end of the paper, including more flexible templates, fixed designs, the agnostic setting, and more. [ABSTRACT FROM AUTHOR]

Mathematical tools that are widely employed for the distribution-free analysis of the finite-sample performance of empirical estimators—like Efron-Stein’s inequality, or Azuma’s martingale inequality and derivatives—rely on the provision of tight bounds for the Lipschitz constants of the estimators. Lipschitz constants can be easily derived for simple functionals of the empirical measures, such as the Shannon or the Tsallis entropy. However, obtaining tight bounds for more generalized entropy functionals which cannot be decomposed into sums of identical terms is much more involved. The goal in this paper is the derivation of (empirical) Lipschitz constants for the maximum likelihood estimator of the family of Renyi entropies of order $\lambda >0$ , $\lambda \neq 1$. Analytic solutions for the optimal constants are obtained for the most important special cases; namely, for $0 < \lambda < 1$ , for $1 < \lambda < 2$ as well as for $\lambda =2$ (collision entropy) and $\lambda = 3$. For the remaining cases where no analytic solution is obtained (i.e., $\lambda > 2$ , $\lambda \neq 3$), an efficient way to compute the optimal constants is derived by reducing the complexity of the underlying optimization problem from exponential ${\varOmega}(n^{\| \mathcal {A} \|-1})$ to linear $\mathcal {O}(n)$ , where $n$ the number of available samples and $\| \mathcal {A} \| \geq 2$ the number of symbols of the source (with the assumption $\| \mathcal {A} \|$ does not grow with $n$). The optimal constants are subsequently used for the distribution-free performance analysis of the maximum likelihood estimator of Renyi entropy; this includes variance and concentration bounds, both under the assumption of independence as well as under strong mixing conditions. [ABSTRACT FROM AUTHOR]

The stochastic block model with two communities, or equivalently the planted bisection model, is a popular model of random graph exhibiting a cluster behavior. In the symmetric case, the graph has two equally sized clusters and vertices connect with probability $p$ within clusters and q$ across clusters. In the past two decades, a large body of literature in statistics and computer science has focused on providing lower bounds on the scaling of |p-q|$ to ensure exact recovery. In this paper, we identify a sharp threshold phenomenon for exact recovery: if \alpha =pn/\log (n)$ and \beta =qn/\log (n)$ are constant (with and is impossible if ({\alpha +\beta }/{2}) - \sqrt {\alpha \beta }<1 . In particular, this improves the existing bounds. This also sets a new line of sight for efficient clustering algorithms. While maximum likelihood (ML) achieves the optimal threshold (by definition), it is in the worst case NP-hard. This paper proposes an efficient algorithm based on a semidefinite programming relaxation of ML, which is proved to succeed in recovering the communities close to the threshold, while numerical experiments suggest that it may achieve the threshold. An efficient algorithm that succeeds all the way down to the threshold is also obtained using a partial recovery algorithm combined with a local improvement procedure. [ABSTRACT FROM PUBLISHER]

This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated random graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the Erdős-Rényi model where the two graphs are subsampled from a common parent Erdős-Rényi graph ${\mathcal {G}}(n,p)$. For dense Erdős-Rényi graphs with $p=n^{-o(1)}$ , we prove that there exists a sharp threshold, above which one can correctly match all but a vanishing fraction of vertices and below which correctly matching any positive fraction is impossible, a phenomenon known as the “all-or-nothing” phase transition. Even more strikingly, in the Gaussian setting, above the threshold all vertices can be exactly matched with high probability. In contrast, for sparse Erdős-Rényi graphs with $p=n^{-\Theta (1)}$ , we show that the all-or-nothing phenomenon no longer holds and we determine the thresholds up to a constant factor. Along the way, we also derive the sharp threshold for exact recovery, sharpening the existing results in Erdős-Rényi graphs. The proof of the negative results builds upon a tight characterization of the mutual information based on the truncated second-moment computation and an “area theorem” that relates the mutual information to the integral of the reconstruction error. The positive results follows from a tight analysis of the maximum likelihood estimator that takes into account the cycle structure of the induced permutation on the edges. [ABSTRACT FROM AUTHOR]

In real life we often deal with independent but not identically distributed observations (i.n.i.d.o), for which the most well-known statistical model is the multiple linear regression model (MLRM) with non-random covariates. While the classical methods are based on the maximum likelihood estimator (MLE), it is well known its lack of robustness to small deviations from the assumed conditions. In this paper, and based on the Rényi’s pseudodistance (RP), we introduce a new family of estimators in case our information about the unknown parameter is given for i.n.i.d.o.. This family of estimators, let us say minimum RP estimators (as they are obtained by minimizing the RP between the assumed distribution and the empirical distribution of the data), contains the MLE as a particular case and can be applied, among others, to the MLRM with non-random covariates. Based on these estimators, we introduce Wald-type tests for testing simple and composite null hypotheses, as an extension of the classical MLE-based Wald test. Influence functions for the estimators and Wald-type tests are also obtained and analysed. Finally, a simulation study is developed in order to asses the performance of the proposed methods and some real-life data are analysed for illustrative purpose. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of estimating the parameters of a Poisson arrival process, where the intensity function is assumed to lie in the span of a known basis. Our goal is to estimate the basis expansions coefficients given a realization of this process. We establish novel guarantees concerning the accuracy achieved by the maximum likelihood estimate. Our initial result is near-optimal, with the exception of an undesirable dependence on the dynamic range of the intensity function. We then show how to remove this dependence through a process of “noise regularization,” which results in an improved bound under our analysis. We conjecture that a similar guarantee should be possible when using a more direct (deterministic) regularization scheme. We conclude with a discussion of practical applications and an empirical examination of the proposed regularization schemes. [ABSTRACT FROM AUTHOR]

This paper develops a new family of estimators, the minimum density power divergence estimators (MDPDEs), for the parameters of the one-shot device model as well as a new family of test statistics, Z-type test statistics based on MDPDEs, for testing the corresponding model parameters. The family of MDPDEs contains as a particular case the maximum likelihood estimator (MLE) considered in Balakrishnan and Ling (2012). Through a simulation study, it is shown that some MDPDEs have a better behavior than the MLE in terms of robustness. At the same time, it can be seen that some Z-type tests based on MDPDEs have a better behavior than the classical Z-test statistic in terms of robustness, as well. [ABSTRACT FROM AUTHOR]

In part I of this two-part work, certain minimization problems based on a parametric family of relative entropies (denoted \mathscr I\alpha ) were studied. Such minimizers were called forward \mathscr I\alpha -projections. Here, a complementary class of minimization problems leading to the so-called reverse \mathscr I\alpha -projections are studied. Reverse \mathscr I\alpha -projections, particularly on log-convex or power-law families, are of interest in robust estimation problems ( $\alpha >1$ ) and in constrained compression settings ( $\alpha <1$ ). Orthogonality of the power-law family with an associated linear family is first established and is then exploited to turn a reverse \mathscr I\alpha -projection into a forward \mathscr I\alpha -projection. The transformed problem is a simpler quasi-convex minimization subject to linear constraints. [ABSTRACT FROM PUBLISHER]

In this paper we consider high-dimensional multiclass classification by sparse multinomial logistic regression. We propose first a feature selection procedure based on penalized maximum likelihood with a complexity penalty on the model size and derive the nonasymptotic bounds for misclassification excess risk of the resulting classifier. We establish also their tightness by deriving the corresponding minimax lower bounds. In particular, we show that there is a phase transition between small and large number of classes. The bounds can be reduced under the additional low noise condition. To find a penalized maximum likelihood solution with a complexity penalty requires, however, a combinatorial search over all possible models. To design a feature selection procedure computationally feasible for high-dimensional data, we propose multinomial logistic group Lasso and Slope classifiers and show that they also achieve the minimax order. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of user activity detection and large-scale fading coefficient estimation in a random access wireless uplink with a massive MIMO base station with a large number M of antennas and a large number of wireless single-antenna devices (users). We consider a block fading channel model where the M-dimensional channel vector of each user remains constant over a coherence block containing L signal dimensions in time-frequency. In the considered setting, the number of potential users Ktot is much larger than L but at each time slot only Ka << Ktot of them are active. Previous results, based on compressed sensing, require that Ka ≤ L, which is a bottleneck in massive deployment scenarios. In this work, we show that such limitation can be overcome when the number of base station antennas M is sufficiently large. More specifically, we prove that with a coherence block of dimension L and a number of antennas M such that Ka/M = o(1), one can identify Ka = O(L2/log2 (Ktot/Ka)) active users, which is much larger than the previously known bounds. We also provide two algorithms. One is based on Non-Negative Least-Squares, for which the above scaling result can be rigorously proved. The other consists of a low-complexity iterative componentwise minimization of the likelihood function of the underlying problem. While for this algorithm a rigorous proof cannot be given, we analyze a constrained version of the Maximum Likelihood (ML) problem (a combinatorial optimization with exponential complexity) and find the same fundamental scaling law for the number of identifiable users. Therefore, we conjecture that the low-complexity (approximated) ML algorithm also achieves the same scaling law and we demonstrate its performance by simulation. We also compare the discussed methods with the (Bayesian) MMV-AMP algorithm, recently proposed for the same setting, and show superior performance and better numerical stability. Finally, we use the discussed approximated ML algorithm as the inner decoder in a concatenated coding scheme for unsourced random access, a grant-free uncoordinated multiple access scheme where all users make use of the same codebook, and the receiver must produce the list of transmitted messages, irrespectively of the identity of the transmitters. We show that reliable communication is possible at any Eb/N0 provided that a sufficiently large number of base station antennas is used, and that a sum spectral efficiency in the order of O(L log (L)) is achievable. [ABSTRACT FROM AUTHOR]

We derive a single-letter upper bound to the mismatched-decoding capacity for discrete memoryless channels. The bound is expressed as the mutual information of a transformation of the channel, such that a maximum-likelihood decoding error on the translated channel implies a mismatched-decoding error in the original channel. In particular, it is shown that if the rate exceeds the upper-bound, the probability of error tends to one exponentially when the block-length tends to infinity. We also show that the underlying optimization problem is a convex-concave problem and that an efficient iterative algorithm converges to the optimal solution. In addition, we show that, unlike achievable rates in the literature, the multiletter version of the bound cannot not improve. A number of examples are discussed throughout the paper. [ABSTRACT FROM AUTHOR]

This paper introduces a convenient strategy for coding and predicting sequences of independent, identically distributed random variables generated from a large alphabet of size $m$ . In particular, the size of the sample is allowed to be variable. The employment of a Poisson model and tilting method simplifies the implementation and analysis through independence. The resulting strategy is optimal within the class of distributions satisfying a moment condition, and it is close to optimal for the class of all i.i.d distributions on strings of a given length. The method also can be used to code and predict strings with a condition on the tail of the ordered counts, and it can be applied to distributions in an envelope class. Moreover, we show that our model permits exact computation of the minimax optimal code, for all alphabet sizes, when conditioning on the size of the sample. [ABSTRACT FROM PUBLISHER]

Recovery of the sparsity pattern (or support) of an unknown sparse vector from a limited number of noisy linear measurements is an important problem in compressed sensing. In the high-dimensional setting, it is known that recovery with a vanishing fraction of errors is impossible if the measurement rate and the per-sample signal-to-noise ratio (SNR) are finite constants, independent of the vector length. In this paper, it is shown that recovery with an arbitrarily small but constant fraction of errors is, however, possible, and that in some cases computationally simple estimators are near-optimal. Bounds on the measurement rate needed to attain a desired fraction of errors are given in terms of the SNR and various key parameters of the unknown vector for several different recovery algorithms. The tightness of the bounds, in a scaling sense, as a function of the SNR and the fraction of errors, is established by comparison with existing information-theoretic necessary bounds. Near optimality is shown for a wide variety of practically motivated signal models. [ABSTRACT FROM PUBLISHER]

This paper considers the asymptotic properties of the recursive maximum-likelihood estimator for hidden Markov models. The paper is focused on the analytic properties of the asymptotic log-likelihood and on the point-convergence and convergence rate of the recursive maximum-likelihood estimator. Using the principle of analytic continuation, the analyticity of the asymptotic log-likelihood is shown for analytically parameterized hidden Markov models. Relying on this fact and some results from differential geometry (Lojasiewicz inequality), the almost sure point convergence of the recursive maximum-likelihood algorithm is demonstrated, and relatively tight bounds on the convergence rate are derived. As opposed to the existing result on the asymptotic behavior of maximum-likelihood estimation in hidden Markov models, the results of this paper are obtained without assuming that the log-likelihood function has an isolated maximum at which the Hessian is strictly negative definite. [ABSTRACT FROM AUTHOR]

We propose a general methodology for the construction and analysis of essentially minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the support size S is unknown and may be comparable with or even much larger than the number of observations n . We treat the respective regions where the functional is nonsmooth and smooth separately. In the nonsmooth regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the smooth regime, we apply a bias-corrected version of the maximum likelihood estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing the performance of the resulting schemes for estimating two important information measures: 1) the entropy H(P) = \sum i = 1^{S} -pi \ln pi and 2) F_\alpha (P) = \sum i = 1^{S} pi^\alpha ,\alpha >0 . We obtain the minimax L2 rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity n \asymp S/\ln S for entropy estimation. We also demonstrate that the sample complexity for estimating F_\alpha (P),0<\alpha <1 , is n\asymp S^1/\alpha / \ln S , which can be achieved by our estimator but not the MLE. For 1<\alpha <3/2 , we show the minimax L2 rate for estimating F_\alpha (P) is (n\ln n)^{-2(\alpha -1)} for infinite support size, while the maximum L2 rate for the MLE is n^{-2(\alpha -1^{^{^{}}})}$ . For all the above cases, the behavior of the minimax rate-optimal estimators with $n$ samples is essentially that of the MLE (plug-in rule) with $n\ln n$ samples, which we term “effective sample size enlargement.” We highlight the practical advantages of our schemes for the estimation of entropy and mutual information. We compare our performance with various existing approaches, and demonstrate that our approach reduces running time and boosts the accuracy. Moreover, we show that the minimax rate-optimal mutual information estimator yielded by our framework leads to significant performance boosts over the Chow–Liu algorithm in learning graphical models. The wide use of information measure estimation suggests that the insights and estimators obtained in this paper could be broadly applicable. [ABSTRACT FROM PUBLISHER]

This paper studies the partial estimation of Gaussian graphical models from high-dimensional empirical observations. We derive a convex formulation for this problem using \ell1-regularized maximum-likelihood estimation, which can be solved via a smoothing approximation algorithm. Statistical estimation performance can be established for our method. The proposed approach has competitive empirical performance compared with existing methods, as demonstrated by various experiments on synthetic and real data sets. [ABSTRACT FROM AUTHOR]

This paper addresses the issue of estimating from a given data sequence the number of mixture components for a Gaussian mixture model(GMM). Our approach is to compute the normalized maximum likelihood (NML) code length for the data sequence relative to a GMM, then to find the mixture size that attains the minimum of the NML on the basis of the minimum description length principle. For finite domains, Kontkanen and Myllymäki proposed a method for efficient computation of the NML code length for specific models, however, for general classes over infinite domains, it has remained open how we compute the NML code length efficiently. We first propose a general method for calculating the NML code length for a general exponential family. Then, we apply it to the efficient computation of the NML code length for a GMM. The key idea is to restrict the data domain in combination with the technique of employing a generating function for computing the normalization term for a GMM. We use artificial datasets to empirically demonstrate that our estimate of the mixture size converges to the true one significantly faster than other criteria. [ABSTRACT FROM AUTHOR]

The minimum description length two-part coding index of resolvability provides a finite-sample upper bound on the statistical risk of penalized likelihood estimators over countable models. However, the bound does not apply to unpenalized maximum likelihood estimation or procedures with exceedingly small penalties. In this paper, we point out a more general inequality that holds for arbitrary penalties. In addition, this approach makes it possible to derive exact risk bounds of order $1/n$ for iid parametric models, which improves on the order $(\log n)/n$ resolvability bounds. We conclude by discussing implications for adaptive estimation. [ABSTRACT FROM AUTHOR]

In this paper, under mild assumptions, we derive a law of large numbers, a central limit theorem with an error estimate, an almost sure invariance principle, and a variant of the Chernoff bound in finite-state hidden Markov models. These limit theorems are of interest in certain areas of information theory and statistics. Particularly, we apply the limit theorems to derive the rate of convergence of the maximum likelihood estimator in finite-state hidden Markov models. [ABSTRACT FROM AUTHOR]

In many signal detection and classification problems, we have knowledge of the distribution under each hypothesis, but not the prior probabilities. This paper is aimed at providing theory to quantify the performance of detection via estimating prior probabilities from either labeled or unlabeled training data. The error or risk is considered as a function of the prior probabilities. We show that the risk function is locally Lipschitz in the vicinity of the true prior probabilities, and the error of detectors based on estimated prior probabilities depends on the behavior of the risk function in this locality. In general, we show that the error of detectors based on the maximum likelihood estimate (MLE) of the prior probabilities converges to the Bayes error at a rate of n^-1/2, where n is the number of training data. If the behavior of the risk function is more favorable, then detectors based on the MLE have errors converging to the corresponding Bayes errors at optimal rates of the form n^-(1+\alpha)/2, where \alpha > 0 is a parameter governing the behavior of the risk function with a typical value \alpha = 1. The limit \alpha \rightarrow \infty corresponds to a situation where the risk function is flat near the true probabilities, and thus insensitive to small errors in the MLE; in this case, the error of the detector based on the MLE converges to the Bayes error exponentially fast with n. We show that the bounds are achievable no matter given labeled or unlabeled training data and are minimax-optimal in the labeled case. [ABSTRACT FROM AUTHOR]

In this paper, a new structured approach for obtaining uniformly best non-Bayesian biased estimators, which attain minimum-mean-square-error performance at any point in the parameter space, is established. We show that if a uniformly best biased (UBB) estimator exists, then it is unique, and it can be directly obtained from any locally best biased (LBB) estimator. A necessary and sufficient condition for the existence of a UBB estimator is derived. It is shown that if there exists an optimal bias, such that this condition is satisfied, then it is unique, and its closed-form expression is obtained. The proposed approach is exemplified in two nonlinear estimation problems, where uniformly minimum-variance-unbiased estimators do not exist. In the considered examples, we show that the UBB estimators outperform the corresponding maximum-likelihood estimators in the MSE sense. [ABSTRACT FROM AUTHOR]

We introduce a new method of data collection for flow size estimation, the optimized flow sampling sketch, which combines the optimal properties of flow sampling with the computational advantages of a counter array sketch. Using Fisher information as a definitive basis of comparison, we show that the statistical efficiency of the method is within a constant factor of that of flow sampling, which is known to be optimal but which cannot be implemented without a flow table, which has higher memory and computational costs. In the process, we derive new results on the Fisher information theoretic and variance properties of the counter array sketch, proving that an overloaded sketch actually destroys information. We revisit the ‘eviction sketch’ of Ribeiro et al. using the Fisher information framework. We show that its performance is much higher than previously supposed, and we define a new method, the optimized eviction sketch, which has very high efficiency. We compare these methods against each other and a third skampling method, sketch guided sampling, theoretically, on models and on data. [ABSTRACT FROM AUTHOR]

The problem of designing good space–time block codes (STBCs) with low maximum-likelihood (ML) decoding complexity has gathered much attention in the literature. All the known low ML decoding complexity techniques utilize the same approach of exploiting either the multigroup decodable or the fast-decodable (conditionally multigroup decodable) structure of a code. We refer to this well-known technique of decoding STBCs as conditional ML (CML) decoding . In this paper, we introduce a new framework to construct ML decoders for STBCs based on the generalized distributive law (GDL) and the factor-graph-based sum–product algorithm. We say that an STBC is fast GDL decodable if the order of GDL decoding complexity of the code, with respect to the constellation size M, is strictly less than M^\lambda, where \lambda is the number of independent symbols in the STBC. We give sufficient conditions for an STBC to admit fast GDL decoding, and show that both multigroup and conditionally multigroup decodable codes are fast GDL decodable. For any STBC, whether fast GDL decodable or not, we show that the GDL decoding complexity is strictly less than the CML decoding complexity. For instance, for any STBC obtained from cyclic division algebras which is not multigroup or conditionally multigroup decodable, the GDL decoder provides about 12 times reduction in complexity compared to the CML decoder. Similarly, for the Golden code, which is conditionally multigroup decodable, the GDL decoder is only half as complex as the CML decoder. [ABSTRACT FROM PUBLISHER]

A two-segment model is introduced here to model the probing process in a network with the tree topology that subsequently leads to four types of explicit estimators to estimate the loss rates of the links within the network. All of the estimators are derived by the maximum likelihood principle, where one of them is developed from an estimator that was used but neglected previously. The estimators are proved to be either unbiased or asymptotic unbiased, and a set of formulae are derived to compute the efficiencies and variances of the estimates obtained by the estimators. One of the formulae shows that if a path is divided into two segments, the variance of the estimates obtained for the pass rate of a segment is equal to the variance of the pass rate of the path divided by the square of the pass rate of the other segment. A number of theorems and corollaries are derived from the formulae to evaluate the performance of an estimator. One of them shows that the estimators derived from the neglected ones are the best in terms of efficiency and computation complexity for the networks of the tree topology. [ABSTRACT FROM PUBLISHER]

We study online learning under logarithmic loss with regular parametric models. In this setting, each strategy corresponds to a joint distribution on sequences. The minimax optimal strategy is the normalized maximum likelihood (NML) strategy. We show that the sequential NML (SNML) strategy predicts minimax optimally (i.e., as NML) if and only if the joint distribution on sequences defined by SNML is exchangeable. This property also characterizes the optimality of a Bayesian prediction strategy. In that case, the optimal prior distribution is Jeffreys prior for a broad class of parametric models for which the maximum likelihood estimator is asymptotically normal. The optimal prediction strategy, NML, depends on the number $n$ of rounds of the game, in general. However, when a Bayesian strategy is optimal, NML becomes independent of $n$ . Our proof uses this to exploit the asymptotics of NML. The asymptotic normality of the maximum likelihood estimator is responsible for the necessity of Jeffreys prior. [ABSTRACT FROM PUBLISHER]

We study the problem of recovering a hidden community of cardinality K from an n \times n symmetric data matrix A , where for distinct indices i,j if i, j both belong to the community and Aij \sim Q otherwise, for two known probability distributions P and Q depending on n . If P=\mathrm Bern(p) and Q=\mathrm Bern(q) with p>q , it reduces to the problem of finding a densely connected K -subgraph planted in a large Erdös–Rényi graph; if P=\mathcal N(\mu ,1) and Q=\mathcal N(0,1) with $\mu >0$ , it corresponds to the problem of locating a K \times K$ principal submatrix of elevated means in a large Gaussian random matrix. We focus on two types of asymptotic recovery guarantees as n \to \infty $ : 1) weak recovery: expected number of classification errors is o(K)$ and 2) exact recovery: probability of classifying all indices correctly converges to one. Under mild assumptions on P$ and Q and ({1-p})/({1-q}) are bounded away from zero and infinity. Previous work has shown that if weak recovery is achievable; then, exact recovery is achievable in linear additional time by a simple voting procedure. We provide a converse, showing the condition for the voting procedure to succeed is almost necessary for exact recovery. [ABSTRACT FROM AUTHOR]

We consider the problem of decentralized scalar parameter estimation using wireless sensor networks with Gaussian noise. Specifically, we propose a novel framework based on level-triggered sampling, a non-uniform sampling strategy, and sequential estimation. The proposed estimator can be used as an asymptotically optimal fixed-sample-size decentralized estimator when the observed Fisher information, i.e., Fisher information without expectation, is deterministic, as an alternative to the one-shot estimators commonly found in the literature. It can also be used as an asymptotically optimal sequential decentralized estimator when the observed Fisher information is random. We show that the optimal centralized estimator under Gaussian noise, which is the maximum likelihood estimator, is characterized by two processes, namely the observed Fisher information Ut and the observed correlation Vt. It is noted that Vt is always random even when Ut is not. In the proposed scheme, each sensor computes its local random processes, and sends a single bit to the fusion center (FC) whenever the local random processes passes certain predefined levels. The FC, upon receiving a bit from a sensor, updates its approximation to the corresponding global random process and, accordingly, its estimate. The sequential estimation process terminates when Ut (or the approximation to it) reaches a target value. We provide an asymptotic analysis for the proposed estimator and the one based on conventional uniform-in-time sampling under both deterministic and random Ut, and determine the conditions under which they are asymptotically optimal, consistent, and asymptotically unbiased. Analytical results, together with simulation results, demonstrate the superiority of the proposed estimator based on level-triggered sampling over the traditional decentralized estimator based on uniform sampling. [ABSTRACT FROM AUTHOR]

We study the phase synchronization problem with measurements ${Y}= {z}^{\ast} {z}^{\ast{\mathrm {H}}}+\sigma {W}\in \mathbb {C}^{n}\times {n}$ , where ${z}^{\ast}$ is an ${n}$ -dimensional complex unit-modulus vector and ${W}$ is a complex-valued Gaussian random matrix. It is assumed that each entry ${Y}_{jk}$ is observed with probability ${p}$. We prove that the minimax lower bound of estimating ${z}^{\ast}$ under the squared $\ell _{2}$ loss is $(1- {o}(1))\frac {\sigma ^{2}}{2p}$. We also show that both generalized power method and maximum likelihood estimator achieve the error bound $(1+ {o}(1))\frac {\sigma ^{2}}{2p}$. Thus, $\frac {\sigma ^{2}}{2p}$ is the exact asymptotic minimax error of the problem. Our upper bound analysis involves a precise characterization of the statistical property of the power iteration. The lower bound is derived through an application of van Trees’ inequality. [ABSTRACT FROM AUTHOR]

Considering the selection of frequency histograms, we propose a modification of Akaike’s Information Criterion that avoids overfitting, even when the sample size is small. We call this correction an over-penalization procedure. We emphasize that the principle of unbiased risk estimation for model selection can indeed be improved by addressing excess risk deviations in the design of the penalization procedure. On the theoretical side, we prove sharp oracle inequalities for the Kullback-Leibler divergence. These inequalities are valid with positive probability for any sample size and include the estimation of unbounded log-densities. Along the proofs, we derive several analytical lemmas related to the Kullback-Leibler divergence, as well as concentration inequalities, that are of independent interest. In a simulation study, we also demonstrate state-of-the-art performance of our over-penalization criterion for bin size selection, in particular outperforming AICc procedure. [ABSTRACT FROM AUTHOR]

We determine the information-theoretic cutoff value on separation of cluster centers for exact recovery of cluster labels in a K-component Gaussian mixture model with equal cluster sizes. Moreover, we show that a semidefinite programming (SDP) relaxation of the K-means clustering method achieves such sharp threshold for exact recovery without assuming the symmetry of cluster centers. [ABSTRACT FROM AUTHOR]

Recent advances in DNA sequencing technology and DNA storage systems have rekindled the interest in deletion channels. Multiple recent works have looked at variants of sequence reconstruction over a single and over multiple deletion channels, a notoriously difficult problem due to its highly combinatorial nature. Although works in theoretical computer science have provided algorithms which guarantee perfect reconstruction with multiple independent observations from the deletion channel, they are only applicable in the large blocklength regime and more restrictively, when the number of observations is also large. Indeed, with only a few observations, perfect reconstruction of the input sequence may not even be possible in most cases. In such situations, maximum likelihood (ML) and maximum aposteriori (MAP) estimates for the deletion channels are natural questions that arise and these have remained open to the best of our knowledge. In this work, we take steps to answer the two aforementioned questions. Specifically: 1. We show that solving for the ML estimate over the single deletion channel (which can be cast as a discrete optimization problem) is equivalent to solving its relaxation, a continuous optimization problem; 2. We exactly compute the symbolwise posterior distributions (under some assumptions on the priors) for both the single as well as multiple deletion channels. As part of our contributions, we also introduce tools to visualize and analyze error events, which we believe could be useful in other related problems concerning deletion channels. [ABSTRACT FROM AUTHOR]

Consider the problem of estimating a latent signal from a lossy compressed version of the data when the compressor is agnostic to the relation between the signal and the data. This situation arises in a host of modern applications when data is transmitted or stored prior to determining the downstream inference task. Given a bitrate constraint and a distortion measure between the data and its compressed version, let us consider the joint distribution achieving Shannon’s rate-distortion (RD) function. Given an estimator and a loss function associated with the downstream inference task, define the RD risk as the expected loss under the RD-achieving distribution. We provide general conditions under which the operational risk in estimating from the compressed data is asymptotically equivalent to the RD risk. The main theoretical tools to prove this equivalence are transportation-cost inequalities in conjunction with properties of compression codes achieving Shannon’s RD function. Whenever such equivalence holds, a recipe for designing estimators from datasets undergoing lossy compression without specifying the actual compression technique emerges: design the estimator to minimize the RD risk. Our conditions are simplified in the special cases of discrete memoryless or multivariate normal data. For these scenarios, we derive explicit expressions for the RD risk of several estimators and compare them to the optimal source coding performance associated with full knowledge of the relation between the latent signal and the data. [ABSTRACT FROM AUTHOR]

Using stochastic gradient search and the optimal filter derivative, it is possible to perform recursive maximum likelihood estimation in a non-linear state-space model. As the optimal filter and its derivative are analytically intractable for such a model, they need to be approximated numerically. In Poyiadjis et al. (G. Poyiadjis, A. Doucet, and S. S. Singh, Biometrika, vol. 98, no. 1, pp. 65–80, 2011), a recursive maximum likelihood algorithm based on a particle approximation to the optimal filter derivative has been proposed and studied through numerical simulations. This algorithm and its asymptotic behavior are here analyzed theoretically. Under regularity conditions, we show that the algorithm accurately estimates maxima of the underlying log-likelihood rate when the number of particles is sufficiently large. We also provide qualitative upper bounds on the estimation error in terms of the number of particles. [ABSTRACT FROM AUTHOR]

Model reduction of Markov processes is a basic problem in modeling state-transition systems. Motivated by the state aggregation approach rooted in control theory, we study the statistical state compression of a discrete-state Markov chain from empirical trajectories. Through the lens of spectral decomposition, we study the rank and features of Markov processes, as well as properties like representability, aggregability, and lumpability. We develop spectral methods for estimating the transition matrix of a low-rank Markov model, estimating the leading subspace spanned by Markov features, and recovering latent structures like state aggregation and lumpable partition of the state space. We prove statistical upper bounds for the estimation errors and nearly matching minimax lower bounds. Numerical studies are performed on synthetic data and a dataset of New York City taxi trips. [ABSTRACT FROM AUTHOR]

Strict Minimum Message Length (SMML) is an information-theoretic statistical inference method widely cited (but only with informal arguments) as providing estimations that are consistent for general estimation problems. It is, however, almost invariably intractable to compute, for which reason only approximations of it (known as MML algorithms) are ever used in practice. Using novel techniques that allow for the first time direct, non-approximated analysis of SMML solutions, we investigate the Neyman-Scott estimation problem, an oft-cited showcase for the consistency of MML, and show that even with a natural choice of prior neither SMML nor its popular approximations are consistent for it, thereby providing a counterexample to the general claim. This is the first known explicit construction of an SMML solution for a natural, high-dimensional problem. [ABSTRACT FROM AUTHOR]

We consider the problem of estimating functionals of discrete distributions, and focus on a tight (up to universal multiplicative constants for each specific functional) nonasymptotic analysis of the worst case squared error risk of widely used estimators. We apply concentration inequalities to analyze the random fluctuation of these estimators around their expectations and the theory of approximation using positive linear operators to analyze the deviation of their expectations from the true functional, namely their bias. We explicitly characterize the worst case squared error risk incurred by the maximum likelihood estimator (MLE) in estimating the Shannon entropy H(P) = \sum i = 1^{S} -pi \ln pi , and the power sum F_\alpha (P) = \sum i = 1^{S} pi^\alpha ,\alpha >0 , up to universal multiplicative constants for each fixed functional, for any alphabet size S\leq \infty and sample size n for which the risk may vanish. As a corollary, for Shannon entropy estimation, we show that it is necessary and sufficient to have n \gg S observations for the MLE to be consistent. In addition, we establish that it is necessary and sufficient to consider samples for the MLE to consistently estimate F_\alpha (P), 0<\alpha <1 . The minimax rate-optimal estimators for both problems require S/\ln S and samples, which implies that the MLE has a strictly sub-optimal sample complexity. When 1<\alpha <3/2 , we show that the worst case squared error rate of convergence for the MLE is n^-2(\alpha -1) for infinite alphabet size, while the minimax squared error rate is (n\ln n)^-2(\alpha -1) . When \alpha \geq 3/2 , the MLE achieves the minimax optimal rate n^{-1} regardless of the alphabet size. As an application of the general theory, we analyze the Dirichlet prior smoothing techniques for Shannon entropy estimation. In this context, one approach is to plug-in the Dirichlet prior smoothed distribution into the entropy functional, while the other one is to calculate the Bayes estimator for entropy under the Dirichlet prior for squared error, which is the conditional expectation. We show that in general such estimators do not improve over the maximum likelihood estimator. No matter how we tune the parameters in the Dirichlet prior, this approach cannot achieve the minimax rates in entropy estimation. The performance of the minimax rate-optimal estimator with n$ samples is essentially at least as good as that of Dirichlet smoothed entropy estimators with $n\ln n$ samples. [ABSTRACT FROM PUBLISHER]

We reveal the relations between the conditional normalized maximum likelihood (CNML) distributions and Bayesian predictive densities based on the latent information priors (LIPs). In particular, CNML3, which is one type of CNML distributions, is investigated. The Bayes projection of a predictive density, which is an information projection of the predictive density on a set of Bayesian predictive densities, is considered. We prove that the sum of the Bayes projection divergence of CNML3 and the conditional mutual information is asymptotically constant. This result implies that the Bayes projection of CNML3 (BPCNML3) is asymptotically identical to the Bayesian predictive density based on LIP. In addition, under some stronger assumptions, we show that BPCNML3 exactly coincides with the Bayesian predictive density based on LIP. [ABSTRACT FROM PUBLISHER]

Lower dimensional signal representation schemes frequently assume that the signal of interest lies in a single vector space. In the context of the recently developed theory of compressive sensing, it is often assumed that the signal of interest is sparse in an orthonormal basis. However, in many practical applications, this requirement may be too restrictive. A generalization of the standard sparsity assumption is that the signal lies in a union of subspaces. Recovery of such signals from a small number of samples has been studied recently in several works. Here, we consider the problem of only subspace recovery in which our goal is to identify the subspace (from the union) in which the signal lies using a small number of samples, in the presence of noise. More specifically, we derive performance bounds and conditions under which reliable subspace recovery is guaranteed using maximum likelihood (ML) estimation. We begin by treating general unions and then obtain the results for the special case in which the subspaces have structure leading to block sparsity. In our analysis, we treat both general sampling operators and random sampling matrices. With general unions, we show that under certain conditions, the number of measurements required for reliable subspace recovery in the presence of noise via ML is less than that implied using the restricted isometry property, which guarantees complete signal recovery. In the special case of block sparse signals, we quantify the gain achievable over standard sparsity in subspace recovery. Our results also strengthen existing results on sparse support recovery in the presence of noise under the standard sparsity model. [ABSTRACT FROM AUTHOR]

It is demonstrated that the sampling distributions of the maximum likelihood (ML) estimator and its Studentized statistic for the generalized Gaussian distribution do not pass the most powerful normality tests even for fairly large sample sizes. This disagreement with what the standard large sample ML theory predicts and the computational burden of having to deal with its associated polygamma functions motivate the consideration of a competing convexity-based estimator. The asymptotic normality of this estimator is derived. It is shown that the competing estimator is almost as efficient as the ML estimator and its asymptotic relative efficiency to the ML estimator is equal to 1 in the limit as the shape parameter approaches zero. More important, its asymptotic distribution admits an exact variance stabilizing transformation, whereas the asymptotic variance function of the ML estimator does not have a closed-form variance stabilizing transformation. The exact transformation is a composition of the inverse hyperbolic cotangent and square root functions. Besides stabilizing the variance, the inverse hyperbolic cotangent and square root transformation is remarkably effective for symmetrizing and normalizing the sampling distribution of the estimator and hence improving the standard normal approximation. Furthermore, this simple transformation provides a quite accurate approximation to the non-closed-form variance stabilizing transformation of the ML estimator. [ABSTRACT FROM AUTHOR]

The problem of clock offset estimation in a two-way timing message exchange regime is considered when the likelihood function of the observation time stamps is Gaussian, exponential, or log-normally distributed. A parameterized solution to the maximum likelihood (ML) estimation of clock offset is analytically obtained, which differs from the earlier approaches where the likelihood function is maximized graphically. In order to capture the imperfections in node oscillators, which may render a time-varying nature to the clock offset, a novel Bayesian approach to the clock offset estimation is proposed by using a factor graph representation of the posterior density. Message passing using the max-product algorithm yields an exact expression for the Bayesian inference problem. Several lower bounds on the variance of an estimator are derived for arbitrary exponential family distributed likelihood functions which, while serving as stepping stones to benchmark the performance of the proposed clock offset estimators, can be useful in their own right in classical as well Bayesian parameter estimation theory. To corroborate the theoretical findings, extensive simulation results are discussed for classical as well as Bayesian estimators in various scenarios. It is observed that the performance of the proposed estimators is fairly close to the fundamental limits established by the lower bounds. [ABSTRACT FROM PUBLISHER]

Threshold effects in the estimation of parameters of nonlinearly modulated, continuous-time, wide-band waveforms, are examined from a statistical physics perspective. These threshold effects are shown to be analogous to phase transitions of certain disordered physical systems in thermal equilibrium. The main message, in this work, is in demonstrating that this physical point of view may be insightful for understanding the interactions between two or more parameters to be estimated, from the aspects of the threshold effect. [ABSTRACT FROM AUTHOR]

The use of information theory concepts for universal estimation of delay for classes of discrete channels is discussed. The problem is presented as one of hypothesis testing. Although the channel statistics are not known, for large enough signal duration, the exponent of the average error probability is equal to that associated with the optimal maximum-likelihood (ML) decision procedure which utilizes full knowledge of the channel parameters. Two categories of problems are discussed: the single-channel problem, where the random transmitted signal is known to the receiver, and the two-sensor problem, where the random signal is unknown. [ABSTRACT FROM PUBLISHER]