Source-linked AI summary
PETRELS: Parallel Subspace Estimation and Tracking by Recursive Least Squares from Partial Observations
Yuejie Chi, Yonina C. Eldar, Robert Calderbank
TL;DR
Recovering a data stream from partial measurements while tracking a changing low-dimensional subspace is important when high-dimensional data are costly to collect. PETRELS uses discounted recursive least squares for parallel row-wise subspace updates, and its reported examples show stronger direction-of-arrival performance than GROUSE and competitiveness with batch matrix-completion methods.
Problem
Online subspace tracking from partial observations is needed when collecting all dimensions of a high-dimensional data stream is costly or impossible.
Source: §I · p. 1Method
PETRELS estimates a subspace through discounted recursive least squares updates performed in parallel for each row, then reconstructs missing entries by least squares when required.
Source: B. PETRELS · p. 4, §VII · p. 11Results
PETRELS distinguishes closely spaced and later-arriving weak modes in direction-of-arrival estimation, tracks subspace changes faster than GROUSE, and is competitive with state-of-the-art batch matrix-completion algorithms.
Source: A. Choice of Parameters · p. 8, B. Direction-Of-Arrival Analysis · p. 9, §VII · p. 11Takeaways & Limitations
The results support PETRELS as an online alternative for partial-observation subspace tracking and fixed-subspace matrix completion.
Source: §VII · p. 11
Abstract
from arXiv · showhide
Many real world data sets exhibit an embedding of low-dimensional structure in a high-dimensional manifold. Examples include images, videos and internet traffic data. It is of great significance to reduce the storage requirements and computational complexity when the data dimension is high. Therefore we consider the problem of reconstructing a data stream from a small subset of its entries, where the data is assumed to lie in a low-dimensional linear subspace, possibly corrupted by noise. We further consider tracking the change of the underlying subspace, which can be applied to applications such as video denoising, network monitoring and anomaly detection. Our problem can be viewed as a sequential low-rank matrix completion problem in which the subspace is learned in an on-line fashion. The proposed algorithm, dubbed Parallel Estimation and Tracking by REcursive Least Squares (PETRELS), first identifies the underlying low-dimensional subspace via a recursive procedure for each row of the subspace matrix in parallel with discounting for previous observations, and then reconstructs the missing entries via least-squares estimation if required. Numerical examples are provided for direction-of-arrival estimation and matrix completion, comparing PETRELS with state of the art batch algorithms.
I. INTRODUCTION
The paper frames online subspace tracking from partial observations as a way to recover high-dimensional data structure with limited measurements. It formalizes the streaming problem and contrasts it with conventional tracking methods, whose covariance updates can be too slow under highly incomplete observations.
I. INTRODUCTION
- Matrix completion and compressive sensing show how structure can be inferred from incomplete measurements, but batch matrix completion corresponds to subspace identification without online tracking.Matrix completion assumes low rank, whereas compressive sensing assumes sparsity in a predetermined basis or dictionary.Source: §I · p. 1
- Online tracking from partial data matters when collecting every dimension is costly or impossible, as in sensor networks and recommendation systems.The motivating goals include low complexity, bounded storage, and timely tracking of subspace changes.Source: §I · p. 1
A. Problem Statement
- Each stream vector is modeled as a low-dimensional subspace combination plus additive white Gaussian noise, with underlying rank allowed to change slowly.The estimated rank is fixed and is assumed to upper-bound the underlying rank.Source: A. Problem Statement · p. 2
- The online estimate uses partial observations to track the changing subspace, with desired low per-step complexity, bounded storage, and convergence when the subspace is constant.The problem statement also calls for timely adaptation to changes.Source: A. Problem Statement · p. 2
B. Conventional Subspace Identification and Tracking
- Conventional power-based tracking converges globally with full observations, but covariance updates become too slow under highly incomplete data, making direct adoption unrealistic.The paper identifies PAST as the closest conventional algorithm and relates PETRELS to it in the full-observation case.Source: B. Conventional Subspace… · pp. 2–3
C. Matrix Completion
The paper connects fixed-subspace matrix completion to recovering a shared low-rank subspace from a stream of partially observed columns. This online formulation can avoid large matrix manipulations before reconstructing the matrix.
C. Matrix Completion
- Batch matrix completion seeks a minimum-rank matrix matching observed entries, but the rank constraint is combinatorially intractable.Nuclear-norm minimization provides a convex alternative that matches the minimum-rank solution under mild conditions.Source: C. Matrix Completion · p. 3
- When the subspace is fixed, matrix completion can be recast as recovering that subspace from a stream of randomly selected columns with partial entries.The sampled columns are presented sequentially with their observation masks.Source: C. Matrix Completion · p. 3
- After estimating the shared subspace, least-squares estimation recovers the low-rank matrix, and the online treatment may avoid large matrix manipulations.The paper compares PETRELS with popular matrix-completion methods.Source: C. Matrix Completion · p. 3
III. THE PETRELS ALGORITHM
PETRELS approximately minimizes geometrically discounted projection residuals on observed entries. Its objective uses discounting to balance fitting a stable subspace against adapting when the underlying subspace changes.
III. THE PETRELS ALGORITHM
- PETRELS is introduced to approximately solve an objective based on total projection residuals over observed entries.The exact optimization is described as difficult and requiring storage of all past observations.Source: §III · p. 3, A. Objective Function · pp. 3–4
A. Objective Function
- The objective estimates a rank-r subspace while geometrically discounting past observations by λ, where 0 < λ ≤ 1.When the subspace is fixed, the objective is minimized at a subspace spanning the underlying structure; λ near 1 reduces forgetting of the past.Source: A. Objective Function · p. 4
- Coefficient constraints can be added through a regularization term, with p = 1 enforcing sparsity and p = 2 enforcing a norm constraint.Source: A. Objective Function · p. 4
- The discount factor controls memory and tracking: values nearer 1 retain more past influence, while discounting supports adaptation to slowly changing subspaces.A time-varying sequence of discount factors is also proposed to control memory and adaptivity more flexibly.Source: A. Objective Function · p. 4
B. PETRELS
PETRELS alternates coefficient estimation with parallel row-wise subspace updates, using recursive least squares to update each row efficiently. It reconstructs the full vector when needed and cautions that long-running fast RLS updates can be numerically unstable.
B. PETRELS
- At each time step, PETRELS estimates coefficients by minimizing projection residual on the previous subspace estimate, then updates the subspace.The algorithm accepts a vector stream and observation pattern, with a random initial subspace and an initialized inverse-related matrix for each row.Source: B. PETRELS · p. 4
- The full vector is estimated from the updated coefficients and subspace, while discounting mitigates error propagation from using updated rather than directly optimized coefficients.The estimated subspace rank is fixed and need not equal the true dimension.Source: B. PETRELS · p. 4
- The subspace update decomposes into smaller problems for each row, enabling parallel row-wise updates.The row estimates are updated recursively using the previous row estimate and RLS update rules.Source: B. PETRELS · pp. 4–5
- Fast RLS updates can suffer finite-precision numerical instability when run for a long time.Source: B. PETRELS · p. 5
C. Second-Order Stochastic Gradient Descent
PETRELS can be viewed as second-order stochastic gradient descent on the discounted objective, using the previous row estimates as a warm start. Its convergence to a stationary point is reported to be faster than for first-order algorithms.
C. Second-Order Stochastic Gradient Descent
- The previous estimate of each subspace row, d_m^(n−1), serves as a warm start at time n.Source: C. Second-Order Stochastic Gradient… · p. 5
- The gradient of F_n(D) at the previous subspace estimate is formed from the row-wise gradient of f_n(D).Source: C. Second-Order Stochastic Gradient… · p. 5
- Each row update can be written as a second-order stochastic-gradient step for the objective.Source: C. Second-Order Stochastic Gradient… · p. 5
- PETRELS converges to a stationary point faster than first-order algorithms, as a second-order stochastic-gradient method.The convergence claim concerns a stationary point of F_n(D).Source: C. Second-Order Stochastic Gradient… · p. 5
D. Comparison with GROUSE
GROUSE performs online subspace identification by alternating coefficient estimation with a first-order update on the orthogonal Grassmannian. The comparison describes its stationary-point guarantee and contrasts its step-size with PETRELS’s discount factor.
D. Comparison with GROUSE
- GROUSE alternates coefficient estimation with a fast rank-one update of the subspace estimate using a first-order gradient on the orthogonal Grassmannian.Source: D. Comparison with GROUSE · p. 5
- GROUSE’s first-order method is guaranteed to converge to a stationary point, but not a global optimum, under mild step-size conditions.Source: D. Comparison with GROUSE · p. 5
- GROUSE may become trapped at a local minimum because of barriers in its Grassmannian search path.The paper contrasts this with PETRELS, whose discount factor is easier to tune than GROUSE’s step-size; with full observations and λ = 1, PETRELS can still converge globally.Source: D. Comparison with GROUSE · p. 5
- Relaxing GROUSE’s objective from orthogonal subspaces to all rank-r subspaces makes it equivalent to PETRELS without discounting.A second-order stochastic-gradient update for this relaxed objective is described, but its performance is not investigated.Source: D. Comparison with GROUSE · pp. 5–6
- In the alternative update, the step-size plays a role similar to PETRELS’s discount parameter, which geometrically weights previous data.Source: D. Comparison with GROUSE · p. 6
E. Complexity Issues
The section compares PETRELS’s storage and computational costs with PAST and GROUSE, then describes a simplified PETRELS variant that reduces storage at a convergence-speed trade-off.
E. Complexity Issues
- PETRELS and GROUSE have computational complexity O(|Ω_t|r^2), while PAST has O(Mr); PETRELS stores O(Mr^2), compared with O(Mr) for PAST and GROUSE.For PETRELS, the larger storage cost is the total size of the R_n matrices for each row.Source: E. Complexity Issues · p. 6
A. Simplified PETRELS
- The simplified update removes the partial-observation operator from the objective and uses the full vector estimate, making the row updates the same across rows.Source: A. Simplified PETRELS · p. 6
- The simplified PETRELS update reduces storage from O(Mr^2) to O(Mr), the size of the subspace.Source: A. Simplified PETRELS · p. 6
- The simplified PETRELS variant converges more slowly than PETRELS but may have an advantage when the subspace rank is underestimated.Source: A. Simplified PETRELS · p. 6
B. Incorporating Prior Information
The paper outlines regularization of the subspace update and analyzes PETRELS’s convergence under full observation. In the partial-observation regime, global convergence remains open; with full observation, PETRELS is shown to converge globally.
B. Incorporating Prior Information
- The proposed subspace regularization uses a positive parameter, but the fast RLS algorithm no longer applies and matrix inversion adds complexity.The regularized expression resembles the matrix-completion formula when V is fixed and composed of columns of a_t.Source: B. Incorporating Prior Information · p. 6
V. GLOBAL CONVERGENCE WITH FULL OBSERVATION
- Under partial observations, PETRELS is known to converge to a stationary point, while whether it reaches the global optimum remains open.Source: §V · p. 6
- With full observations, PETRELS is equivalent in its convergence dynamics to PAST and converges to the global optimum.Source: §V · pp. 6–7
VI. NUMERICAL RESULTS
The numerical section examines PETRELS’ parameter sensitivity and tracking under partial observations, and reports superior direction-of-arrival performance versus GROUSE and competitiveness with batch matrix-completion algorithms.
VI. NUMERICAL RESULTS
- PETRELS is reported superior to GROUSE for direction-of-arrival estimation and at least competitive with state-of-the-art batch algorithms for matrix completion.The numerical results also include simulations of PETRELS extensions.Source: §VI · p. 7
A. Choice of Parameters
- With 50 of 500 entries observed and no noise, normalized subspace reconstruction error is minimized around λ = 0.98, which the experiments use thereafter.The rank is set accurately to 10 and the run continues to n = 2000.Source: A. Choice of Parameters · p. 7, Figure 1 · p. 7
- Overestimating rank degrades convergence gracefully; the study tests estimates of 10, 12, 14, 16, and 18 and focuses on overestimation as the usual application case.Rank underestimation is examined in the next section.Source: A. Choice of Parameters · p. 7
- Increasing the number of observed entries per time step speeds convergence, and PETRELS works when that count is close to the theoretical lower bound of about 23 measurements.The theoretical bound is M ∼ O(r log r) ≈ 23 for testing whether an incomplete vector lies in a rank-r subspace [14].Source: A. Choice of Parameters · p. 7
- As noise level ǫ increases, subspace error degrades gracefully and converges to an error floor determined by the noise variance.Source: A. Choice of Parameters · p. 7
- For rank-10 subspaces changing abruptly at indices 3000 and 5000 with rank overestimated by 4, both PETRELS and GROUSE track the change, but PETRELS does so faster.The noise level is ǫ = 10^-3.Source: A. Choice of Parameters · pp. 7–8
B. Direction-Of-Arrival Analysis
In dynamic direction-of-arrival simulations, PETRELS identifies closely spaced and weak modes and tracks mode changes more successfully than GROUSE; the study estimates frequencies from the learned subspace using ESPRIT.
B. Direction-Of-Arrival Analysis
- The direction-of-arrival simulation uses a 256-sensor linear array, Gaussian noise with ǫ = 0.1, and measurements from 30 randomly selected sensors per time step.The model represents modes with frequencies and amplitudes.Source: B. Direction-Of-Arrival Analysis · p. 8
- ESPRIT is applied to the estimated subspace to recover mode frequencies from eigenvalues of the transformation between its shifted row blocks [29].The eigenvalue arguments are scaled by 1/(2π) to obtain the frequencies.Source: B. Direction-Of-Arrival Analysis · p. 8
- In a dynamic setting with a varying subspace, PETRELS does better than GROUSE at discarding outdated modes and picking up new ones.Source: B. Direction-Of-Arrival Analysis · p. 8
- The dynamic scenario changes two frequencies at stream index 1000, adds a mode at 2000, and deletes the weakest mode at 3000.Source: B. Direction-Of-Arrival Analysis · pp. 8–9
- PETRELS identifies all modes, including three closely spaced modes and later weak modes, and tracks their changes; GROUSE merges close modes, misses weak modes, introduces spurious modes, and does not react to model changes.Both methods estimate 10 modes, twice the number of true modes in this scenario; PETRELS’s auxiliary modes appear as low-amplitude scatter points.Source: B. Direction-Of-Arrival Analysis · p. 9
C. Matrix Completion
For matrix completion, PETRELS matches batch algorithms on Gaussian data and improves the accuracy of most on uniform data; the paper also reports rank-dependent behavior for simplified PETRELS. The conclusion describes PETRELS as a discounted, parallel subspace-tracking method with competitive matrix-completion performance.
D. Simplified PETRELS
- With rank overestimated as 12, simplified PETRELS adds errors and converges more slowly; with rank underestimated as 8, it performs better, apparently helped by interpolated entries.The authors state that quantitative justification for this behavior is beyond the paper’s scope.Source: D. Simplified PETRELS · pp. 10–11
C. Matrix Completion
- PETRELS matches batch algorithms on Gaussian data and improves upon most algorithms’ accuracy on uniform data, while the authors conclude it is competitive overall.The simulation used a rank-10 factorization of a 1000 × 2000 matrix with 5% of entries revealed; the authors note it shows one realization.Source: C. Matrix Completion · p. 10, Figure 8 · p. 11
VII. CONCLUSIONS
- PETRELS estimates the subspace through discounted, parallel row-wise recursion, then reconstructs missing entries by least squares if required.The discount factor is described as supporting both long-term behavior and tracking changes in the data stream.Source: §VII · p. 11
- The paper reports convergence to a stationary point and global convergence in the full-observation scenario through PETRELS’s connection with PAST.It also reports superior direction-of-arrival performance and competitive performance against state-of-the-art batch matrix-completion algorithms.Source: §VII · p. 11