The group fused Lasso for multiple change-point detection

Kevin Bleakley; Jean-Philippe Vert

Source-linked AI summary

The group fused Lasso for multiple change-point detection

Kevin Bleakley, Jean-Philippe Vert

arXiv:1106.4199v1Jun 21, 2011q-bio.QMstat.ML

TL;DR

The paper addresses efficient detection of change-points shared across multiple one-dimensional signals, where standard global segmentation can be too costly. It introduces a multidimensional total-variation formulation with exact and approximate solvers, and reports consistency for single change-points while multiple-change-point consistency remains conjectural.

Problem
Efficiently segment multidimensional signals with shared change-points, since global dynamic programming has prohibitive quadratic complexity in signal length.
Method
The group fused Lasso extends total-variation denoising using a multidimensional increment penalty and provides exact group Lasso and approximate group LARS solvers.
Results
The method consistently estimates a single change-point under the stated increasing-profile asymptotics, with weighted penalties correcting boundary effects.
Takeaways & Limitations
Increasing the number of profiles is theoretically and empirically beneficial for detecting approximately shared change-points.
Takeaways & Limitations
Consistency for multiple change-points is conjectured under certain conditions rather than established by the presented theory.

Abstract

from arXiv · show

We present the group fused Lasso for detection of multiple change-points shared by a set of co-occurring one-dimensional signals. Change-points are detected by approximating the original signals with a constraint on the multidimensional total variation, leading to piecewise-constant approximations. Fast algorithms are proposed to solve the resulting optimization problems, either exactly or approximately. Conditions are given for consistency of both algorithms as the number of signals increases, and empirical evidence is provided to support the results on simulated and array comparative genomic hybridization data.

1 Introduction

The paper targets shared change-points across multiple one-dimensional signals, motivated by applications including genomics. It develops computationally efficient total-variation methods and studies their behavior as the number of profiles increases.

Shared change-point detection identifies locations where most or all one-dimensional signals change together.
Dynamic programming solves optimal k-segment multidimensional signals in O(n^2pk), which is prohibitive for genomic profiles with very large n.
Binary segmentation is faster, but its segmentation quality can be questionable relative to global procedures.
Total variation replaces the non-convex jump count with a convex penalty, yielding piecewise-constant approximations with theoretical change-point guarantees for single signals.
The proposed multidimensional extension uses a quadratic error and summed Euclidean norms, with exact group Lasso and approximate group LARS algorithms.
The theory focuses on fixed profile length and increasing dimension, matching settings where more patients or samples provide additional profiles.
The paper evaluates the method theoretically and empirically, including copy-number variation analysis in cancer.

2 Notation

This section establishes interval, norm, matrix-subsetting, row, column, ones-matrix, and identity-matrix notation used later.

For integers u ≤ v, [u, v] denotes the integer interval from u through v.
The notation defines Frobenius norms and matrix submatrices indexed by row and column sets.
A bullet denotes all columns or rows, while 1u,v and Ip denote the u × v ones matrix and p × p identity matrix.

3 Formulation

The formulation models multiple noisy profiles with shared change-points and extends one-dimensional total variation through a multidimensional convex penalty. The resulting problem has a group Lasso representation that supports efficient computation and shared segmentation.

3 Formulation: Profiles are modeled as noisy piecewise-constant signals whose change-point locations tend to be shared.
3.1 Segmentation with a total variation penalty: The single-profile objective seeks a piecewise-constant approximation with at most k jumps, but dynamic programming requires O(n^2k).
3.1 Segmentation with a total variation penalty: Convex total variation relaxes jump-count minimization and can be solved more efficiently than the combinatorial formulation.
3.1 Segmentation with a total variation penalty: The multidimensional penalty sums Euclidean norms of profile increments, encouraging increment vectors to vanish at common positions across profiles.
3.1 Segmentation with a total variation penalty: Position-dependent weights generalize the uniform penalty, whose boundary effects make weighted schemes theoretically and empirically preferable.
3.1 Segmentation with a total variation penalty: In simulated profiles, joint TV denoising is compared with independent TV denoising for the first five detected change-points.
3.2 Reformulation as a group Lasso problem: A change of variables expresses weighted jumps through β and an intercept γ, then centers the data to eliminate the optimal γ.
3.2 Reformulation as a group Lasso problem: The centered formulation is a classical group Lasso whose feature groups are rows of β, and its solution maps back to the original profile approximation.

4 Implementation

The implementation develops efficient exact and approximate solvers for the group Lasso formulation, exploiting the problem’s structure to handle very large dimensions. It uses active-set block coordinate descent for exact optimization and group LARS for approximate regularization paths.

Computational challenge: General-purpose solvers are impractical at dimensions reaching millions because the design matrix is dense and too large to store.The multidimensional design matrix has size n × (n − 1), and existing single-profile methods do not directly apply when p > 1.
Algorithms: Two algorithms solve the optimization problem efficiently: one exactly and one approximately, both exploiting the regression design’s particular structure.The implementation adopts group-Lasso algorithms and supplies efficient operations for the structured design matrix.
Exact solver: Block coordinate descent optimizes groups iteratively and converges to the global optimum, with KKT conditions used to monitor convergence.Each group corresponds to a potential change-point, and an active-set strategy restricts optimization to non-zero groups while adding or removing groups when KKT conditions are violated.
Exact solver: The active-set implementation alternates optimization over active groups with KKT-based updates to avoid processing all n − 1 groups repeatedly.This strategy is motivated by the expectation that only a fraction of groups are non-zero at the optimum.
Exact solver: Each active-set group-optimization iteration costs O(|A|p), with total optimization expected to be at least quadratic in |A| and linear in p.The stated per-iteration costs include O(|A|) for a structured matrix operation, O(|A|p) for computing S_i, and O(p) for soft-thresholding.
Approximate solver: Group LARS approximately traces the regularization path by adding change-points one at a time and moving along descent directions between additions.Structured computational tricks avoid storing the design matrix; key operations include computing X̄^⊤Ȳ in O(np) and the descent direction using active-set computations.

5 Theoretical analysis

The paper analyzes consistency when the profile length is fixed and the number of signals increases, focusing first on single shared change-points and then on fluctuating positions. Unweighted group fused Lasso has boundary and noise-dependent limitations, while suitable weighting yields position-robust consistency; multiple-change-point consistency remains unresolved.

Theoretical analysis: The analysis reverses the usual asymptotic regime by fixing profile length n and increasing the number of profiles p.This setting is motivated by genomics, where additional samples or patients increase p while the measurement technology fixes n.
Single change-point: The group fused Lasso selects the first change-point by maximizing a criterion G_i with probability tending to 1 as p increases.This characterization provides the basis for the consistency results for weighted and unweighted procedures.
Single change-point: For the unweighted procedure, consistent detection depends on the change-point position and noise level, with boundary locations harder to identify.For fixed noise, detection is asymptotically correct over an interior interval, and increasing n expands that interval relative to the profile length.
Single change-point: The unweighted group fused Lasso suffers boundary effects because excessive noise can shift estimated change-points toward the middle of the interval.The paper states that larger noise produces greater bias and motivates weighted penalties to address this issue.
Weighted procedure: The weighted group fused Lasso correctly finds a single change-point at any position with probability tending to 1 as p increases.The weighting scheme is described as canceling the noise effect and enabling consistency independently of position.
Fluctuating positions: With fluctuating change-point locations across profiles, the weighted method identifies a change-point within the support of the location distribution asymptotically without conditions on noise or support.The unweighted method achieves this only under specified noise and support conditions.
Multiple change-points: The theoretical results do not establish consistency for multiple change-points, which the paper postpones to future work.The authors conjecture consistency under conditions involving noise and sufficient separation and directional difference between successive change-points.

6 Experiments

Experiments evaluate computational efficiency, single- and multiple-change-point accuracy, and cancer aCGH applications. The group fused Lasso generally improves accuracy over group fused LARS, while matching or greatly exceeding competing methods in speed.

Experimental setup: The experiments used simulated profiles spanning varied lengths, dimensions, and numbers of shared change-points, alongside real aCGH datasets.The implementations were run in MATLAB, with experiments covering both computational efficiency and detection accuracy.
Computational efficiency: Group fused LARS remained practically fast, with even the longest speed trials averaging less than 200 seconds.Its scaling was clearest as linear in k, while curves for n and p were initially sub-linear and later slightly super-linear.
Computational efficiency: When seeking 100 change-points, Lasso was 1,000 times slower than LARS because their empirical complexities in k were cubic and linear, respectively.This difference became most pronounced as the number of change-points increased.
Accuracy: For single change-points, unweighted accuracy converged toward 1 for 50 ≤ u < 80 and toward zero for u > 80 as p increased.The weighted method remained robust to fluctuations in the exact change-point location.
Accuracy: For multiple change-points, exact group fused Lasso outperformed group fused LARS, while weighted versions outperformed unweighted versions across noise levels.Accuracy was measured by recovery of all nine true change-points at positions 10, 20, ..., 90.
Cancer applications: On the first aCGH benchmark, weighted group fused LARS achieved AUC 0.97 in 0.06 seconds versus H-HMM’s AUC 0.96±.01 in 60.20 seconds.The methods had similar performance, but weighted group fused LARS was around 1000 times faster.
Cancer applications: On lung and bladder cancer datasets, weighted group fused LARS was substantially faster than H-HMM and recovered genomic regions consistent with known recurrent alterations.It took 4.7 seconds versus 38 minutes for the lung-cell-line dataset and 1.1 seconds versus 13 minutes for bladder profiles.

7 Conclusion

The paper extends total-variation approximation to multidimensional signals through the group fused Lasso and develops exact and approximate solvers. Its theory and experiments support consistent shared-change-point detection, especially as the number of profiles increases, while the method estimates only shared changes.

Contribution: The group fused Lasso extends total-variation approximation to multidimensional signals and has exact and approximate optimization algorithms.The resulting convex problem uses a quadratic error penalized by Euclidean norms of multidimensional increments.
Findings: The method consistently estimates a single change-point theoretically and empirically, with experimental evidence suggesting similar behavior for multiple change-points.The conclusion distinguishes established single-change-point consistency from the empirical evidence for several change-points.
Findings: Increasing the number of profiles benefits detection of approximately shared change-points, supporting applications involving accumulating genomic patient data.The stated genomic scope concerns detecting common genomic alterations.
Scope: The method estimates only shared change-points, effectively targeting their union rather than change-points specific to individual profiles.Individual-profile changes would require post-processing or modifying the formulation with additional penalties.

Annex A: Computational lemmas

The annex derives fast matrix operations needed by the group LARS and group fused Lasso implementations. Cumulative-sum recurrences and matrix structure reduce key computations to linear or active-set-scaled complexity.

Fast matrix products: The centered design matrix enables computing X̄ᵀR in O(np) time and memory using cumulative sums.The procedure forms row-wise cumulative sums and then computes each output row from the total and partial sums.
Algorithmic implications: The group LARS descent direction can be computed in O(|A|p) and O(np) stages, while descent-step coefficients lead to overall O(np) complexity.The implementation avoids storing and manipulating the full design matrix.
Fast matrix products: The product X̄ᵀX̄R can also be computed in O(np) time and memory through diagonal scaling and forward-backward recurrences.The method constructs intermediate matrices using cumulative sums and successive row updates.
Fast matrix products: When R is row-sparse, the first two steps of the X̄ᵀX̄R computation cost O(sp), where s is the number of nonzero rows.This yields a practical speed-up when s ≪ n, although the overall computation remains O(np).
Active-set computations: The inverse of the relevant structured matrix is tridiagonal, allowing successive rows of the required products to be computed from only a few terms.This structure supports O(|A|p) time and memory for active-set submatrices.

Annex B: Proof of Lemma 1

The proof analyzes which candidate location first enters the group fused Lasso solution by comparing norm-based statistics across positions. As p increases, the maximizer of the limiting statistic is selected with probability tending to one.

First change-point: The constant solution persists while the KKT conditions hold, and the first change-point appears when λ reaches the largest candidate norm.The selected location is the row attaining the maximum Euclidean norm of the transformed data matrix.
Distributional analysis: The transformed candidate rows are jointly Gaussian, with their means and covariances determined by the single nonzero change-point row.The proof defines Fi as the Euclidean norm of the candidate row statistics.
Asymptotic selection: For each candidate location, Fi/p converges in probability to a location-dependent limit as the number of profiles increases.The limiting comparison is expressed through the statistics Gi.
Asymptotic selection: The probability of selecting a location maximizing Gi converges to one as p → +∞.A union-bound argument shows that the best limiting candidates eventually dominate all nonmaximizers.

Annex C: Proof of Theorem 2

The proof reduces correct first change-point selection to whether G_u is the global maximum. It establishes threshold conditions under which G_u exceeds neighboring candidates.

The first selected change-point lies in argmax_i G_i with probability tending to 1 as p increases.Correct selection therefore depends on whether the true position u maximizes G_i.
For i from u to n−1, G_i decreases, so G_u is always maximal over that interval.The remaining comparison is restricted to indices from 1 through u.
For i from 1 to u, G_i is a second-order polynomial that is zero at 0 and positive at u, so G_u is maximal there exactly when G_u > G_{u−1}.
When α > 1/2 + 1/(2n), G_u > G_{u−1} exactly when σ < σ̃.
When α equals 1/2 or 1/2 + 1/(2n), G_u > G_{u−1} always holds.

Annex D: Proof of Theorem 3

The proof substitutes the weighting scheme into G_i and shows that the resulting criterion increases up to the true change-point and decreases afterward. Thus, the maximizer is the true position u.

Substituting the weights d_i into G_i yields a piecewise expression whose behavior determines whether the method selects u.
The resulting expression increases on [1,u] and decreases on [u,n−1].
Therefore, argmax_i G_i over i from 1 to n−1 equals u, and the result follows from Lemma 1.

Annex E: Proof of Theorem 4

The proof analyzes G_i when the change-point distribution is supported on an interval [a,b]. It shows that the selected position remains within this support under the considered weighting schemes, with probability tending to 1 as p increases.

The proof estimates F_i and uses independence of the signal parameters and noise to obtain a probability limit for F_i/p.
The method selects the corresponding position with probability tending to 1 as p increases.
Assuming the change-point support is [a,b], the proof studies G_i separately before a and under two possible weighting schemes.
The maximum of G_i cannot be below a or above b, so it lies within [a,b], the support of P_U.
When n/2 lies in [a,b], the selected position belongs to [a,b] for any σ_2 > 0.
If a > n/2, the maximum is not before a exactly when G_a > G_{a−1}, which holds when σ_2 < σ̃_2.