We provide the asymptotic minimax detection boundary for a bump, i.e. an abrupt change, in the mean function of a dependent Gaussian process. This will be characterized in terms of the asymptotic behaviour of the bump length and height as well as the dependency structure of the process. A major finding is that for stationary processes the asymptotic minimax detection boundary is generically determined by the value of is spectral density at zero. Hence, a positive long-run variance makes detection harder whereas a negative long-run variance eases bump detection. Finally, our asymptotic analysis is complemented by non-asymptotic results for the subclass of AR( @math ) processes and confirmed to serve as a good proxy for finite sample scenarios in a simulation study. Our proofs are based on laws of large numbers for non-independent and non-identically distributed arrays of random variables and the asymptotically sharp analysis of the precision matrix of the process.
The literature for dependent noise is much less developed, and most similar in spirit to our work are the papers by and . In the former, the minimax detection boundary for an unstructured version of the model in a Bayesian setting is derived, this is @math and @math with a probability @math tending to @math . In contrast to @cite_5 , in the present setting we can borrow strength from neighboring observations in a bump. Still, we can exploit a result in about the decay behavior of inverses of covariance matrices (see Section in the Appendix) to validate Assumption .
@cite_5
2088633674 2047838040 2127184781 1980652450
Abstract In this paper, we model linear inverse problems with long-range dependence by a fractional Gaussian noise model and study function estimation based on observations from the model. By using two wavelet-vaguelette decompositions, one for the inverse problem which simultaneously quasi-diagonalizes both the operator and the prior information, and one for long-range dependence which decorrelates fractional Gaussian noise, we establish asymptotics for minimax risks, and show that the wavelet shrinkage estimate can be tuned to achieve the minimax convergence rate and significantly outperform linear estimates. In this article we study function estimation via wavelet shrinkage for data with long-range dependence. We propose a fractional Gaussian noise model to approximate nonparametric regression with long-range dependence and establish asymptotics for minimax risks. Because of long-range dependence, the minimax risk and the minimax linear risk converge to 0 at rates that differ from those for data with independence or short-range dependence. Wavelet estimates with best selection of resolution leveldependent threshold achieve minimax rates over a wide range of spaces. Cross-validation for dependent data is proposed to select the optimal threshold. The wavelet estimates significantly outperform linear estimates. The key to proving the asymptotic results is a wavelet]vaguelette decomposition which decorrelates fractional Gaussian noise. Such wavelet]vaguelette decomposition is also very useful in fractal signal processing. We consider the non-parametric estimation of a function that is observed in white noise after convolution with a boxcar, the indicator of an interval ( a; a). In a recent paper Johnstone, Kerkyacharian, Picard and Raimondo (2004) have developed a wavelet deconvolution method (called WaveD) that can be used for " boxcar kernels. For example, WaveD can be tuned to achieve near optimal rates over Besov spaces when a is a Badly Approximable (BA) irrational number. While the set of all BA's contains quadratic irrationals, e.g., a = p 5, it has Lebesgue measure zero. In this paper we derive two tuning scenarios of WaveD that are valid for all" boxcar convolutions (i.e., when a 2 A where A is a full Lebesgue measure set). We propose (i) a tuning inspired from Minimax theory over Besov spaces; (ii) a tuning derived from Maxiset theory providing similar rates as for WaveD in the BA widths setting. Asymptotic theory nds that (i) in the worst case scenario, departures from the BA assumption aect WaveD convergence rates, at most, by log factors; (ii) the Maxiset tuning, which yields smaller thresholds, is superior to the Minimax tuning over a whole range of Besov sub-scales. Our asymptotic results are illustrated in an extensive simulation of boxcar convolution observed in white noise. This paper considers the inverse problem with observed variables Y = BGX ⊕Z, where BG is the incidence matrix of a graph G, X is the vector of unknown vertex variables with a uniform prior, and Z is a noise vector with Bernoulli(e) i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery of X is possible if and only the graph G is connected, with a sharp threshold at the edge probability log(n) n for Erdős-Renyi random graphs. The first goal of this paper is to determine how the edge probability p needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by α = np log(n), it is shown that exact recovery is possible if and only if α > 2 (1−2e)+o(1 (1−2e)). In other words, 2 (1−2e) is the information theoretic threshold for exact recovery at lowSNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. Full version available in [1].