Search

We consider the related problems of estimating the $l_2$-norm and the squared $l_2$-norm in sparse linear regression with unknown variance, as well as the problem of testing the hypothesis that the regression parameter is null under sparse alternatives with $l_2$ separation. We establish the minimax optimal rates of estimation (respectively, testing) in these three problems.

In this paper, we observe a sparse mean vector through Gaussian noise and we aim at estimating some additive functional of the mean in the minimax sense. More precisely, we generalize the results of (Collier et al., 2017, 2019) to a very large class of functionals. The optimal minimax rate is shown to depend on the polynomial approximation rate of the marginal functional, and optimal estimators achieving this rate are built.

We study the problem of estimation of the value N_gamma(\theta) = sum(i=1)^d |\theta_i|^gamma for 0 < gamma <= 1 based on the observations y_i = \theta_i + \epsilon\xi_i, i = 1,...,d, where \theta = (\theta_1,...,\theta_d) are unknown parameters, \epsilon>0 is known, and \xi_i are i.i.d. standard normal random variables. We prove that the non-asymptotic minimax risk on the class B_0(s) of s-sparse vectors and we propose estimators achieving the minimax rate.

We consider the problem of testing the hypothesis that the parameter of linear regression model is 0 against an s-sparse alternative separated from 0 in the l2-distance. We show that, in Gaussian linear regression model with p < n, where p is the dimension of the parameter and n is the sample size, the non-asymptotic minimax rate of testing has the form sqrt((s/n) log(1 + sqrt(p)/s )). We also show that this is the minimax rate of estimation of the l2-norm of the regression parameter.

For the sparse vector model, we consider estimation of the target vector, of its L2-norm and of the noise variance. We construct adaptive estimators and establish the optimal rates of adaptive estimation when adaptation is considered with respect to the triplet "noise level - noise distribution - sparsity". We consider classes of noise distributions with polynomially and exponentially decreasing tails as well as the case of Gaussian noise. The obtained rates turn out to be different from the minimax non-adaptive rates when the triplet is known. A crucial issue is the ignorance of the noise variance. Moreover, knowing or not knowing the noise distribution can also influence the rate. For example, the rates of estimation of the noise variance can differ depending on whether the noise is Gaussian or sub-Gaussian without a precise knowledge of the distribution. Estimation of noise variance in our setting can be viewed as an adaptive variant of robust estimation of scale in the contamination model, where instead of fixing the "nominal" distribution in advance, we assume that it belongs to some class of distributions.

We consider two problems of estimation in high-dimensional Gaussian models. The first problem is that of estimating a linear functional of the means of $n$ independent $p$-dimensional Gaussian vectors, under the assumption that most of these means are equal to zero. We show that, up to a logarithmic factor, the minimax rate of estimation in squared Euclidean norm is between $(s^2\wedge n) +sp$ and $(s^2\wedge np)+sp$. The estimator that attains the upper bound being computationally demanding, we investigate suitable versions of group thresholding estimators that are efficiently computable even when the dimension and the sample size are very large. An interesting new phenomenon revealed by this investigation is that the group thresholding leads to a substantial improvement in the rate as compared to the element-wise thresholding. Thus, the rate of the group thresholding is $s^2\sqrt{p}+sp$, while the element-wise thresholding has an error of order $s^2p+sp$. To the best of our knowledge, this is the first known setting in which leveraging the group structure leads to a polynomial improvement in the rate. The second problem studied in this work is the estimation of the common $p$-dimensional mean of the inliers among $n$ independent Gaussian vectors. We show that there is a strong analogy between this problem and the first one. Exploiting it, we propose new strategies of robust estimation that are computationally tractable and have better rates of convergence than the other computationally tractable robust (with respect to the presence of the outliers in the data) estimators studied in the literature. However, this tractability comes with a loss of the minimax-rate-optimality in some regimes.

Assume that we observe a sample of size n composed of p-dimensional signals, each signal having independent entries drawn from a scaled Poisson distribution with an unknown intensity. We are interested in estimating the sum of the n unknown intensity vectors, under the assumption that most of them coincide with a given 'background' signal. The number s of p-dimensional signals different from the background signal plays the role of sparsity and the goal is to leverage this sparsity assumption in order to improve the quality of estimation as compared to the naive estimator that computes the sum of the observed signals. We first introduce the group hard thresholding estimator and analyze its mean squared error measured by the squared Euclidean norm. We establish a nonasymptotic upper bound showing that the risk is at most of the order of {\sigma}^2(sp + s^2sqrt(p)) log^3/2(np). We then establish lower bounds on the minimax risk over a properly defined class of collections of s-sparse signals. These lower bounds match with the upper bound, up to logarithmic terms, when the dimension p is fixed or of larger order than s^2. In the case where the dimension p increases but remains of smaller order than s^2, our results show a gap between the lower and the upper bounds, which can be up to order sqrt(p).

We consider the problem of estimation of a linear functional in the Gaussian sequence model where the unknown vector theta in R^d belongs to a class of s-sparse vectors with unknown s. We suggest an adaptive estimator achieving a non-asymptotic rate of convergence that differs from the minimax rate at most by a logarithmic factor. We also show that this optimal adaptive rate cannot be improved when s is unknown. Furthermore, we address the issue of simultaneous adaptation to s and to the variance sigma^2 of the noise. We suggest an estimator that achieves the optimal adaptive rate when both s and sigma^2 are unknown.

For the Gaussian sequence model, we obtain non-asymptotic minimax rates of estimation of the linear, quadratic and the L2-norm functionals on classes of sparse vectors and construct optimal estimators that attain these rates. The main object of interest is the class s-sparse vectors for which we also provide completely adaptive estimators (independent of s and of the noise variance) having only logarithmically slower rates than the minimax ones. Furthermore, we obtain the minimax rates on the Lq-balls where 0 < q < 2. This analysis shows that there are, in general, three zones in the rates of convergence that we call the sparse zone, the dense zone and the degenerate zone, while a fourth zone appears for estimation of the quadratic functional. We show that, as opposed to estimation of the vector, the correct logarithmic terms in the optimal rates for the sparse zone scale as log(d/s^2) and not as log(d/s). For the sparse class, the rates of estimation of the linear functional and of the L2-norm have a simple elbow at s = sqrt(d) (boundary between the sparse and the dense zones) and exhibit similar performances, whereas the estimation of the quadratic functional reveals more complex effects and is not possible only on the basis of sparsity described by the sparsity condition on the vector. Finally, we apply our results on estimation of the L2-norm to the problem of testing against sparse alternatives. In particular, we obtain a non-asymptotic analog of the Ingster-Donoho-Jin theory revealing some effects that were not captured by the previous asymptotic analysis., Comment: 32 pages

The problem of matching two sets of features appears in various tasks of computer vision and can be often formalized as a problem of permutation estimation. We address this problem from a statistical point of view and provide a theoretical analysis of the accuracy of several natural estimators. To this end, the minimax rate of separation is investigated and its expression is obtained as a function of the sample size, noise level and dimension. We consider the cases of homoscedastic and heteroscedastic noise and establish, in each case, tight upper bounds on the separation distance of several estimators. These upper bounds are shown to be unimprovable both in the homoscedastic and heteroscedastic settings. Interestingly, these bounds demonstrate that a phase transition occurs when the dimension $d$ of the features is of the order of the logarithm of the number of features $n$. For $d=O(\log n)$, the rate is dimension free and equals $\sigma (\log n)^{1/2}$, where $\sigma$ is the noise level. In contrast, when $d$ is larger than $c\log n$ for some constant $c>0$, the minimax rate increases with $d$ and is of the order $\sigma(d\log n)^{1/4}$. We also discuss the computational aspects of the estimators and provide empirical evidence of their consistency on synthetic data. Finally, we show that our results extend to more general matching criteria.

This paper is concerned with the problem of goodness-of-fit for curve registration, and more precisely for the shifted curve model, whose application field reaches from computer vision and road traffic prediction to medicine. We give bounds for the asymptotic minimax separation rate, when the functions in the alternative lie in Sobolev balls and the separation from the null hypothesis is measured by the l2-norm. We use the generalized likelihood ratio to build a nonadaptive procedure depending on a tuning parameter, which we choose in an optimal way according to the smoothness of the ambient space. Then, a Bonferroni procedure is applied to give an adaptive test over a range of Sobolev balls. Both achieve the asymptotic minimax separation rates, up to possible logarithmic factors.

The problem of curve registration appears in many different areas of applications ranging from neuroscience to road traffic modeling. In the present work, we propose a nonparametric testing framework in which we develop a generalized likelihood ratio test to perform curve registration. We first prove that, under the null hypothesis, the resulting test statistic is asymptotically distributed as a chi-squared random variable. This result, often referred to as Wilks' phenomenon, provides a natural threshold for the test of a prescribed asymptotic significance level and a natural measure of lack-of-fit in terms of the $p$-value of the $\chi^2$-test. We also prove that the proposed test is consistent, \textit{i.e.}, its power is asymptotically equal to $1$. Finite sample properties of the proposed methodology are demonstrated by numerical simulations. As an application, a new local descriptor for digital images is introduced and an experimental evaluation of its discriminative power is conducted.