High-dimensional change-point estimation: combining filtering with convex optimization
From MaRDI portal
Publication:2397167
Abstract: We consider change-point estimation in a sequence of high-dimensional signals given noisy observations. Classical approaches to this problem such as the filtered derivative method are useful for sequences of scalar-valued signals, but they have undesirable scaling behavior in the high-dimensional setting. However, many high-dimensional signals encountered in practice frequently possess latent low-dimensional structure. Motivated by this observation, we propose a technique for high-dimensional change-point estimation that combines the filtered derivative approach from previous work with convex optimization methods based on atomic norm regularization, which are useful for exploiting structure in high-dimensional data. Our algorithm is applicable in online settings as it operates on small portions of the sequence of observations at a time, and it is well-suited to the high-dimensional setting both in terms of computational scalability and of statistical efficiency. The main result of this paper shows that our method performs change-point estimation reliably as long as the product of the smallest-sized change (the Euclidean-norm-squared of the difference between signals at a change-point) and the smallest distance between change-points (number of time instances) is larger than a Gaussian width parameter that characterizes the low-dimensional complexity of the underlying signal sequence.
Recommendations
- Change detection via affine and quadratic detectors
- High dimensional change point estimation via sparse projection
- High-dimensional change-point detection under sparse alternatives
- Generalized multiple change-point detection in the structure of multivariate, possibly high-dimensional, data sequences
- Inference on the change point under a high dimensional sparse mean shift
Cites work
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A local method for estimating change points: the “Hat-function”
- A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
- Atomic Norm Denoising With Applications to Line Spectral Estimation
- Compressed sensing
- Compressed Sensing Off the Grid
- Computational and statistical tradeoffs via convex relaxation
- Computational Sample Complexity
- Computational sample complexity and attribute-efficient learning
- Computing the nearest correlation matrix--a problem from finance
- CONTINUOUS INSPECTION SCHEMES
- Corrupted Sensing: Novel Guarantees for Separating Structured Signals
- Covariance regularization by thresholding
- De-noising by soft-thresholding
- Decentralized quickest change detection
- Detection of abrupt changes: theory and application
- Exact matrix completion via convex optimization
- From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
- Geometry of cuts and metrics
- Global optimization with polynomials and the problem of moments
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- High-dimensional change-point detection under sparse alternatives
- High-dimensional graphs and variable selection with the Lasso
- scientific article; zbMATH DE number 3883450 (Why is no real title available?)
- scientific article; zbMATH DE number 4061904 (Why is no real title available?)
- scientific article; zbMATH DE number 3320765 (Why is no real title available?)
- scientific article; zbMATH DE number 3369559 (Why is no real title available?)
- Hyperbolic programs, and their derivative relaxations
- Inferring Rankings Using Constrained Sensing
- Living on the edge: phase transitions in convex programs with random data
- Most tensor problems are NP-hard
- Multiple Change-Point Estimation With a Total Variation Penalty
- Multiple-Change-Point Detection for High Dimensional Time Series via Sparsified Binary Segmentation
- Near-ideal model selection by \(\ell _{1}\) minimization
- Null space conditions and thresholds for rank minimization
- Off-Line Detection of Multiple Change Points by the Filtered Derivative withp-Value Method
- On Optimum Methods in Quickest Detection Problems
- On the Best 2-CUSUM Stopping Rule for Quickest Detection of Two-Sided Alternatives in a Brownian Motion Model
- On the monotonicity of the gradient of a convex function
- Optimal detection of sparse principal components in high dimension
- Optimal Shrinkage of Singular Values
- Probability of unique integer solution to a system of linear equations
- Procedures for Reacting to a Change in Distribution
- Proximité et dualité dans un espace hilbertien
- Regularized estimation of large covariance matrices
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Some remarks on greedy algorithms
- Tensor Decompositions and Applications
- The concentration of measure phenomenon
- The convex geometry of linear inverse problems
- Theta bodies for polynomial ideals
- Universal approximation bounds for superpositions of a sigmoidal function
- Wild binary segmentation for multiple change-point detection
Cited in
(8)- Change-point detection in panel data via double CUSUM statistic
- Online multivariate changepoint detection with type I error control and constant time/memory updates per series
- Sequential change point detection in high dimensional time series
- On change-point estimation under Sobolev sparsity
- High dimensional change point estimation via sparse projection
- False discovery rate approach to dynamic change detection
- Inference in High-Dimensional Online Changepoint Detection
- A kernel multiple change-point algorithm via model selection
This page was built for publication: High-dimensional change-point estimation: combining filtering with convex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397167)
