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]

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]

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]

Minimizing the divergence between two probability distributions offers an alternative parameter estimation method. The current literature mainly focuses on minimizing the Kullback-Leibler (K-L) divergence between the true and the proposed models in which the true model is assumed to be known or fixed. In this paper, we propose a parameter estimation method that minimizes the $f$ -divergence between two probability distributions. The method is suitable for different situations, no matter the true distribution is known or not. The statistical properties of the estimator, including consistency and asymptotic normality, are established. As an illustration, our method is employed to estimate the degradation model, which is a model frequently used to assess the lifetime of highly reliable products. A simulation study and a real degradation data analysis are presented to illustrate the effectiveness of the proposed estimation method. [ABSTRACT FROM AUTHOR]

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 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 provides a precise error analysis for the maximum likelihood estimate $\hat {\textit a}_{\text {ML}}({\textit u}_{1}^{\textit n})$ of the parameter ${\textit a}$ given samples ${\textit u}_{1}^{\textit n} = ({\textit u}_{1}, \ldots, {\textit u}_{\textit n})'$ drawn from a nonstationary Gauss-Markov process ${\textit U}_{\textit i} = {\textit a} {\textit U}_{\textit i-1} + {\textit Z}_{\textit i},\,\,{\textit i}\geq 1$ , where ${\textit U}_{0} = 0$ , ${\textit a}> 1$ , and ${\textit Z}_{\textit i}$ ’s are independent Gaussian random variables with zero mean and variance $\sigma ^{2}$. We show a tight nonasymptotic exponentially decaying bound on the tail probability of the estimation error. Unlike previous works, our bound is tight already for a sample size of the order of hundreds. We apply the new estimation bound to find the dispersion for lossy compression of nonstationary Gauss-Markov sources. We show that the dispersion is given by the same integral formula that we derived previously for the asymptotically stationary Gauss-Markov sources, i.e., $|{\textit a}| < 1$. New ideas in the nonstationary case include separately bounding the maximum eigenvalue (which scales exponentially) and the other eigenvalues (which are bounded by constants that depend only on a) of the covariance matrix of the source sequence, and new techniques in the derivation of our estimation error bound. [ABSTRACT FROM AUTHOR]

This paper considers the problem of estimating a high-dimensional vector of parameters \theta \in \mathbb R^n from a noisy observation. The noise vector is independent identically distributed Gaussian with known variance. For a squared-error loss function, the James–Stein (JS) estimator is known to dominate the simple maximum-likelihood (ML) estimator when the dimension n exceeds two. The JS-estimator shrinks the observed vector toward the origin, and the risk reduction over the ML-estimator is greatest for {\theta } that lie close to the origin. JS-estimators can be generalized to shrink the data toward any target subspace. Such estimators also dominate the ML-estimator, but the risk reduction is significant only when {\theta } lies close to the subspace. This leads to the question: in the absence of prior information about \theta , how do we design estimators that give significant risk reduction over the ML-estimator for a wide range of \theta ? In this paper, we propose shrinkage estimators that attempt to infer the structure of \theta from the observed data in order to construct a good attracting subspace. In particular, the components of the observed vector are separated into clusters, and the elements in each cluster shrunk toward a common attractor. The number of clusters and the attractor for each cluster are determined from the observed vector. We provide concentration results for the squared-error loss and convergence results for the risk of the proposed estimators. The results show that the estimators give significant risk reduction over the ML-estimator for a wide range of \theta , particularly for large $n$ . Simulation results are provided to support the theoretical claims. [ABSTRACT FROM AUTHOR]

Linear regression without correspondences is the problem of performing a linear regression fit to a dataset for which the correspondences between the independent samples and the observations are unknown. Such a problem naturally arises in diverse domains such as computer vision, data mining, communications and biology. In its simplest form, it is tantamount to solving a linear system of equations, for which the entries of the right hand side vector have been permuted. This type of data corruption renders the linear regression task considerably harder, even in the absence of other corruptions, such as noise, outliers or missing entries. Existing methods are either applicable only to noiseless data or they are very sensitive to initialization or they work only for partially shuffled data. In this paper we address these issues via an algebraic geometric approach, which uses symmetric polynomials to extract permutation-invariant constraints that the parameters $\xi ^{*} \in \mathbb {R} ^{\text {n}}$ of the linear regression model must satisfy. This naturally leads to a polynomial system of n equations in n unknowns, which contains $\xi ^{*}$ in its root locus. Using the machinery of algebraic geometry we prove that as long as the independent samples are generic, this polynomial system is always consistent with at most n! complex roots, regardless of any type of corruption inflicted on the observations. The algorithmic implication of this fact is that one can always solve this polynomial system and use its most suitable root as initialization to the Expectation Maximization algorithm. To the best of our knowledge, the resulting method is the first working solution for small values of n able to handle thousands of fully shuffled noisy observations in milliseconds. [ABSTRACT FROM AUTHOR]

Data, which lie in the space \mathcal Pm\, , of $m \times m$ symmetric positive definite matrices, (sometimes called tensor data), play a fundamental role in applications, including medical imaging, computer vision, and radar signal processing. An open challenge, for these applications, is to find a class of probability distributions, which is able to capture the statistical properties of data in \mathcal Pm\, , as they arise in real-world situations. The present paper meets this challenge by introducing Riemannian Gaussian distributions on \mathcal Pm\, . Distributions of this kind were first considered by Pennec in 2006. However, the present paper gives an exact expression of their probability density function for the first time in existing literature. This leads to two original contributions. First, a detailed study of statistical inference for Riemannian Gaussian distributions, uncovering the connection between the maximum likelihood estimation and the concept of Riemannian centre of mass, widely used in applications. Second, the derivation and the implementation of an expectation-maximisation algorithm, for the estimation of mixtures of Riemannian Gaussian distributions. The paper applies this new algorithm, to the classification of data in \mathcal Pm\, , (concretely, to the problem of texture classification, in computer vision), showing that it yields significantly better performance, in comparison to recent approaches. [ABSTRACT FROM PUBLISHER]

This paper studies forward and reverse projections for the Rényi divergence of order $\alpha \in (0, \infty )$ on $\alpha $ -convex sets. The forward projection on such a set is motivated by some works of Tsallis et al. in statistical physics, and the reverse projection is motivated by robust statistics. In a recent work, van Erven and Harremoës proved a Pythagorean inequality for Rényi divergences on $\alpha $ -convex sets under the assumption that the forward projection exists. Continuing this study, a sufficient condition for the existence of a forward projection is proved for probability measures on a general alphabet. For $\alpha \in (1, \infty )$ , the proof relies on a new Apollonius theorem for the Hellinger divergence, and for $\alpha \in (0,1)$ , the proof relies on the Banach–Alaoglu theorem from the functional analysis. Further projection results are then obtained in the finite alphabet setting. These include a projection theorem on a specific $\alpha $ -convex set, which is termed an $\alpha $ -linear family, generalizing a result by Csiszár to $\alpha \neq 1$ . The solution to this problem yields a parametric family of probability measures, which turns out to be an extension of the exponential family, and it is termed an $\alpha $ -exponential family. An orthogonality relationship between the $\alpha $ -exponential and $\alpha $ -linear families is established, and it is used to turn the reverse projection on an $\alpha $ -exponential family into a forward projection on an $\alpha $ -linear family. This paper also proves a convergence result of an iterative procedure used to calculate the forward projection on an intersection of a finite number of $\alpha $ -linear families. [ABSTRACT FROM PUBLISHER]

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]

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 this paper, we propose a general framework for tensor singular value decomposition (tensor singular value decomposition (SVD)), which focuses on the methodology and theory for extracting the hidden low-rank structure from high-dimensional tensor data. Comprehensive results are developed on both the statistical and computational limits for tensor SVD. This problem exhibits three different phases according to the signal-to-noise ratio (SNR). In particular, with strong SNR, we show that the classical higher-order orthogonal iteration achieves the minimax optimal rate of convergence in estimation; with weak SNR, the information-theoretical lower bound implies that it is impossible to have consistent estimation in general; with moderate SNR, we show that the non-convex maximum likelihood estimation provides optimal solution, but with NP-hard computational cost; moreover, under the hardness hypothesis of hypergraphic planted clique detection, there are no polynomial-time algorithms performing consistently in general. [ABSTRACT FROM AUTHOR]

Suppose that we are given a time series where consecutive samples are believed to come from a probabilistic source, that the source changes from time to time and that the total number of sources is fixed. Our objective is to estimate the distributions of the sources. A standard approach to this problem is to model the data as a hidden Markov model (HMM). However, since the data often lacks the Markov or the stationarity properties of an HMM, one can ask whether this approach is still suitable or perhaps another approach is required. In this paper, we show that a maximum likelihood HMM estimator can be used to approximate the source distributions in a much larger class of models than HMMs. Specifically, we propose a natural and fairly general non-stationary model of the data, where the only restriction is that the sources do not change too often. Our main result shows that for this model, a maximum-likelihood HMM estimator produces the correct second moment of the data, and the results can be extended to higher moments. [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]

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]

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]

Resolving a conjecture of Abbe, Bandeira, and Hall, the authors have recently shown that the semidefinite programming (SDP) relaxation of the maximum likelihood estimator achieves the sharp threshold for exactly recovering the community structure under the binary stochastic block model (SBM) of two equal-sized clusters. The same was shown for the case of a single cluster and outliers. Extending the proof techniques, in this paper, it is shown that SDP relaxations also achieve the sharp recovery threshold in the following cases: 1) binary SBM with two clusters of sizes proportional to network size but not necessarily equal; 2) SBM with a fixed number of equal-sized clusters; and 3) binary censored block model with the background graph being Erdős–Rényi. Furthermore, a sufficient condition is given for an SDP procedure to achieve exact recovery for the general case of a fixed number of clusters plus outliers. These results demonstrate the versatility of SDP relaxation as a simple, general purpose, computationally feasible methodology for community detection. [ABSTRACT FROM AUTHOR]

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]

This paper examines a general class of noisy matrix completion tasks, where the goal is to estimate a matrix from observations obtained at a subset of its entries, each of which is subject to random noise or corruption. Our specific focus is on settings where the matrix to be estimated is well-approximated by a product of two (a priori unknown) matrices, one of which is sparse. Such structural models—referred to here as sparse factor models—have been widely used, for example, in subspace clustering applications, as well as in contemporary sparse modeling and dictionary learning tasks. Our main theoretical contributions are estimation error bounds for sparsity-regularized maximum likelihood estimators for the problems of this form, which are applicable to a number of different observation noise or corruption models. Several specific implications are examined, including scenarios where observations are corrupted by additive Gaussian noise or additive heavier-tailed (Laplace) noise, Poisson-distributed observations, and highly quantized (e.g., 1 b) observations. We also propose a simple algorithmic approach based on the alternating direction method of multipliers for these tasks, and provide experimental evidence to support our error analyses. [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]

Graph clustering involves the task of dividing nodes into clusters, so that the edge density is higher within clusters as opposed to across clusters. A natural, classic, and popular statistical setting for evaluating solutions to this problem is the stochastic block model, also referred to as the planted partition model. In this paper, we present a new algorithm—a convexified version of maximum likelihood—for graph clustering. We show that, in the classic stochastic block model setting, it outperforms existing methods by polynomial factors when the cluster size is allowed to have general scalings. In fact, it is within logarithmic factors of known lower bounds for spectral methods, and there is evidence suggesting that no polynomial time algorithm would do significantly better. We then show that this guarantee carries over to a more general extension of the stochastic block model. Our method can handle the settings of semirandom graphs, heterogeneous degree distributions, unequal cluster sizes, unaffiliated nodes, partially observed graphs, planted clique/coloring, and so on. In particular, our results provide the best exact recovery guarantees to date for the planted partition, planted \( k \) -disjoint-cliques and planted noisy coloring models with general cluster sizes; in other settings, we match the best existing results up to logarithmic factors. [ABSTRACT FROM AUTHOR]

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 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]

This paper presents the theoretical foundation for time-domain, phase-based estimation of the frequency and phase of a single sinusoid in additive white Gaussian noise (AWGN), analogous to the theoretical foundation provided by Rife and Boorstyn for frequency-domain, Fourier-transform-based estimation. It is shown from the maximum a posteriori probability (MAP) and the maximum likelihood (ML) estimation principles that with the additive observation phase noise (AOPN), due to the AWGN, being described by its a posteriori distribution conditioned on the received signal magnitude, the received signal phase is a sufficient statistic for estimating the single-sinusoid angle parameters. Using a geometric approach, the exact statistical model for the AOPN is derived, where the a posteriori probability density function (pdf) and the corresponding a priori pdf are given by explicit, closed-form expressions that are valid for arbitrary signal-to-noise ratios (SNRs). The a posteriori pdf is Tikhonov, and is of particular interest as it establishes the AOPN model for phase-based frequency/phase MAP/ML estimation in the time domain. It is further illustrated that the results derived can yield various AOPN models as special cases, and the underlying physical insights and interconnections that exist among these models are revealed. It is shown that the model derived by Tretter is an ultimate specialization in the high SNR limit of the AOPN models developed here. For high SNR, the a posteriori Tikhonov pdf can be accurately approximated by a Gaussian distribution, which leads to the best linearized AOPN model. The applications of these AOPN models to the design of linear estimators, including the linear minimum mean square error (LMMSE) estimator, the linear minimum variance estimator, and the LMMSE implementation of the weighted phase averager are presented, and their estimation performances are compared through computer simulations, with the Cramer–Rao lower bound (CRLB) and the Bayesian CRLB as the benchmark. To facilitate estimator design, the a priori statistical models of the frequency and phase are proposed from the information-theoretic perspective, and an improved phase unwrapping algorithm over that given by Fu and Kam is presented. It is shown that by incorporating all the information available in the AOPN, the estimation accuracy can be much improved. [ABSTRACT FROM PUBLISHER]

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]

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]

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]