|
Is it possible to detect if the sample paths of a stochastic process almost surely admit a finite expansion with respect to some/any basis? The determination is to be made on the basis of a finite collection of discretely/noisily observed sample paths. We show that it is indeed possible to construct a hypothesis testing scheme that is almost surely guaranteed to make only finite many incorrect decisions as more data are collected. Said differently, our scheme almost certainly detects whether the process has a finite or infinite basis expansion for all sufficiently large sample sizes. Our approach relies on Cover's classical test for the irrationality of a mean, combined with tools for the non-parametric estimation of covariance operators . Introduction Let { X ( t ) : t ∈ [ 0 , 1 ] } be a second-order stochastic process, with almost surely continuous sample paths. We wish to discern whether there exists a deterministic Orthonormal Basis (ONB) { ψ l } of L 2 [ 0 , 1 ] and a finite constant L < ∞ such that X ( t ) = ∑ l = 1 L 〈 X , ψ l 〉 ψ l ( t ) , almost surely , where 〈 ⋅ , ⋅ 〉 is the L 2 inner product and equality is almost everywhere; i.e. we wish to discern whether the realisations of the stochastic process are entirely contained in some finite dimensional subspace of L 2 , with probability 1. Alternatively, we might wish to discern whether the displayed equality holds true for a specific ONB and some constant L < ∞ , i.e. whether the paths of the process a.s. admit a finite expansion in a given basis. Of course, if we assume that X ( t ) can be observed in full, then both questions become moot: as soon as we observe n > L realisations we can know with (almost) certainty whether X lies in a finite dimensional subspace of dimension L ; and, even with a single realisation, we can a.s. know whether 〈 X , ψ l 〉 vanishes for all but finitely many elements of a given ONB { ψ l } . However, we are interested in a setting where we can only observe finitely many noisy point evaluations on each of n independently realised sample paths of X . In this case, the answer to either question becomes far from obvious, since 〈 X , ψ l 〉 needs to be estimated. Such questions are very natural from a theoretical point of view. They ask whether an a priori infinite dimensional signal is, in fact, finite dimensional (in a given or any dictionary). And, they ask whether it's possible to detect a “tail property” on the basis of finite and corrupted data. Such questions lie at the intersection of data compression, signal processing, and statistics. Indeed, they are at the heart of functional data analysis (see e.g. [7], [12]), where methodology to make inferences on stochastic processes typically relies heavily on optimal dimension reduction, and where “ one has always a finite number of realizations from which one is to infer aspects of the infinite-dimensional probabilistic generating mechanism” (Donoho et al. [5, p. 2448]). In this paper, we construct a testing method that is proven to err only finitely often except on a negligible set, see Theorem 1, Theorem 2. In this sense, it is able to detect whether the law of the process is supported on a subspace spanned by finitely many elements of some/any ONB (and if so, what the dimension of this subspace is). Our method is inspired by Cover's [2] approach to determining whether the mean of a sequence of real-valued random variables is rational or irrational (see also Donoho [4] and Dembo and Peres [3]). We suitably adapt it to our needs by translating it to a question on the finiteness of the spectral decomposition of the process' second-moment operator. Spruill [11] asked a related question, also adopting Cover's perspective, namely whether the mean of a stochastic process admits a finite expansion. Our setting and contributions are distinct in important ways. First, we are concerned with the almost sure representation of the process itself, rather than its mean. This not only has immediate statistical applications, but also induces notable differences, conceptual and technical, as we focus on the covariance structure (fluctuations of the process) rather than the mean (location of the process) function itself. Second, and perhaps more important, we assume discrete/noisy observation of sample paths, rather than perfect observation.1 Finally, a mean function can always be finitely represented in the ONB whose first element is the mean itself. Therefore, the question we ask on whether the sample paths can be finitely expanded in some basis (rather than just a specific basis) is genuinely novel. Our work is also distinct from previous testing methodology developed in the context of functional data analysis ([8], [6], [1]). These papers focus on whether the process is of dimension at most L 0 for some given and fixed L 0 < ∞ . By contrast, we wish to detect whether the process is of some finite dimension without prescribing which dimension. Thus, our process will detect any finite dimension (not upper bounded by an a priori guess), and will also be able to detect infinite dimensionality (as opposed to detecting that the dimension exceeds a pre-specified upper bound L 0 ). Section snippets Basic definitions and problem statement Let H = L 2 ( [ 0 , 1 ] ) be the Hilbert space of square integrable real-valued functions on the unit interval, equipped with the usual inner product 〈 ⋅ , ⋅ 〉 and norm ‖ ⋅ ‖ . The class of Hilbert Schmidt operators and nuclear operators on H will be denoted by S and N , respectively. We use the notation ‖ ⋅ ‖ S and ‖ ⋅ ‖ N to indicate the corresponding norms on S and N , ‖ A ‖ S = trace { A ⁎ A } & ‖ A ‖ N = trace { A ⁎ A } , where A ⁎ denotes the adjoint of a bounded linear operator A . The inner product on S will be denoted by 〈 A , B 〉 S = trace { A ⁎ B Preliminaries Our testing strategy will be to use an estimator G ˆ n = G ˆ n ( { Y m l } ) that is consistent for G at a rate that is almost surely bounded by some known sequence R ( n ) under both the null and alternative regimes, see Assumption 1 below. Specific estimators will yield specific forms of R ( n ) based on sufficient regularity conditions on G . We will restrict our framework to specific choices, but rather develop our theoretical results by assuming a general form (see Remark 1 for examples of specific choices Implementation In the present section we provide a concrete implementation of the procedure, by way of providing examples of estimators G ˆ n and prior measures ν (and associated sequences { k ( j ) } and { n ( j ) } ), as required in Algorithm 1, Algorithm 2 (and Theorem 1, Theorem 2). Proof of Lemma 1 Proof of Lemma 1 To prove part 1, note that the direct statement is immediate i.e. if the law of X is supported on some finite dimensional subspace of H then the covariance operator C is of finite rank. For the converse, when C is of finite rank, L say, the process admits the Karhunen-Loève decomposition X ( t ) = μ ( t ) + ∑ l = 1 L 〈 X − μ , ϕ l 〉 ϕ l ( t ) , with { ϕ l } l = 1 ∞ the Karhunen-Loève basis, extended to an ONB for the whole space. Let P L = ∑ l = 1 L ϕ l ⊗ ϕ l be the projector onto the subspace spanned by the first L Karhunen-Loève basis Acknowledgement We are very thankful to a reviewer and to the Editor for constructive feedback that genuinely helped improve the paper. References (12) C. Spruill Determining the form of the mean of a stochastic process J. Multivar. Anal. (1977) A. Chakraborty et al. Testing for the rank of a covariance operator Ann. Stat. (2022) T.M. Cover On determining the irrationality of the mean of a random variable Ann. Stat. (1973) A. Dembo et al. A topological criterion for hypothesis testing Ann. Stat. (1994) D.L. Donoho One-sided inference about functionals of a density Ann. Stat. (1988) D.L. Donoho et al. Data compression and harmonic analysis IEEE Trans. Inf. Theory (1998) There are more references available in the full text version of this article. Cited by (0) Recommended articles (6) Research article On the frame set of the second-order B-spline Applied and Computational Harmonic Analysis, Volume 62, 2023, pp. 237-250 Show abstract The frame set of a function g ∈ L 2 ( R ) is the set of all parameters ( a , b ) ∈ R + 2 for which the collection of time-frequency shifts of g along a Z × b Z form a Gabor frame for L 2 ( R ) . Finding the frame set of a given function remains a challenging open problem in time-frequency analysis. In this paper, we establish new regions of the frame set of the second-order B-spline. Our method uses the compact support of this function to partition a subset of the putative frame set and finds an explicit dual window function in each subregion. Numerical evidence indicates the existence of further regions belonging to the frame set. Research article Rate-optimal sparse approximation of compact break-of-scale embeddings Applied and Computational Harmonic Analysis, Volume 65, 2023, pp. 40-66 Show abstract The paper is concerned with the sparse approximation of functions having hybrid regularity borrowed from the theory of solutions to electronic Schrödinger equations due to Yserentant (2004) [42] . We use hyperbolic wavelets to introduce corresponding new spaces of Besov- and Triebel-Lizorkin-type to particularly cover the energy norm approximation of functions with dominating mixed smoothness. Explicit adaptive and non-adaptive algorithms are derived that yield sharp dimension-independent rates of convergence. Research article Frames by orbits of two operators that commute Applied and Computational Harmonic Analysis, Volume 66, 2023, pp. 46-61 Show abstract Frames formed by orbits of vectors through the iteration of a bounded operator have recently attracted considerable attention, in particular due to its applications to dynamical sampling. In this article, we consider two commuting bounded operators acting on some separable Hilbert space H . We completely characterize operators T and L with T L = L T and sets Φ ⊂ H such that the collection { T k L j ϕ : k ∈ Z , j ∈ J , ϕ ∈ Φ } forms a frame of H . This is done in terms of model subspaces of the space of square integrable functions defined on the torus and having values in some Hardy space with multiplicity. The operators acting on these models are the bilateral shift and the compression of the unilateral shift (acting pointwisely). This context includes the case when the Hilbert space H is a subspace of L 2 ( R ) , invariant under translations along the integers, where the operator T is the translation by one and L is a shift-preserving operator. Research article Super-resolution of generalized spikes and spectra of confluent Vandermonde matrices Applied and Computational Harmonic Analysis, Volume 65, 2023, pp. 181-208 Show abstract We study the problem of super-resolution of a linear combination of Dirac distributions and their derivatives on a one-dimensional circle from noisy Fourier measurements. Following numerous recent works on the subject, we consider the geometric setting of “partial clustering”, when some Diracs can be separated much below the Rayleigh limit. Under this assumption, we prove sharp asymptotic bounds for the smallest singular value of a corresponding rectangular confluent Vandermonde matrix with nodes on the unit circle. As a consequence, we derive matching lower and upper min-max error bounds for the above super-resolution problem, under the additional assumption of nodes belonging to a fixed grid. Research article A simple approach for quantizing neural networks Applied and Computational Harmonic Analysis, Volume 66, 2023, pp. 138-150 Show abstract In this short note, we propose a new method for quantizing the weights of a fully trained neural network. A simple deterministic pre-processing step allows us to quantize network layers via memoryless scalar quantization while preserving the network performance on given training data. On one hand, the computational complexity of this pre-processing slightly exceeds that of state-of-the-art algorithms in the literature. On the other hand, our approach does not require any hyper-parameter tuning and, in contrast to previous methods, allows a plain analysis. We provide rigorous theoretical guarantees in the case of quantizing single network layers and show that the relative error decays with the number of parameters in the network if the training data behave well, e.g., if it is sampled from suitable random distributions. The developed method also readily allows the quantization of deep networks by consecutive application to single layers. Research article Spectral graph wavelet packets frames Applied and Computational Harmonic Analysis, Volume 66, 2023, pp. 18-45 Show abstract Classical wavelet, wavelet packets and time-frequency dictionaries have been generalized to the graph setting, the main goal being to obtain atoms which are jointly localized both in the vertex and the graph spectral domain. We present a new method to generate a whole dictionary of frames of wavelet packets defined in the graph spectral domain to represent signals on weighted graphs. We will give some concrete examples on how the spectral graph wavelet packets can be used for compressing, denoising and reconstruction by considering a signal, given by the fRMI (functional magnetic resonance imaging) data, on the nodes of voxel-wise brain graph with 900760 nodes, representing the brain voxels. View full text © 2023 Elsevier Inc. All rights reserved. About ScienceDirect Remote access Shopping cart Advertise Contact and support Terms and conditions Privacy policy We use cookies to help provide and enhance our service and tailor content and ads. By continuing you agree to the use of cookies . Copyright © 2023 Elsevier B.V. or its licensors or contributors. ScienceDirect® is a registered trademark of Elsevier B.V. ScienceDirect® is a registered trademark of Elsevier B.V.
|
