PaperlayerView exact revision on arXiv

Source-linked AI summary

Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors

Morteza Mardani, Gonzalo Mateos, Georgios B. Giannakis

arXiv:1404.4667v1stat.MLcs.ITcs.LG

TL;DR

High-dimensional, incomplete data create challenges for timely analytics, especially when processing must occur in real time. This paper develops online methods for matrix subspace estimation and low-rank tensor decomposition, with convergence results and performance demonstrated under substantial missingness.

  • Problem

    High-dimensional datasets can contain sizable portions of missing data, complicating timely data analytics.

  • Method

    The paper proposes exponentially weighted least-squares estimation with nuclear-norm regularization and develops online algorithms for matrix imputation and low-rank tensor decomposition.

  • Results

    The proposed online algorithms asymptotically converge and attain the global optimum of the batch nuclear-norm-regularized estimator, including tests with up to 75% missing entries.

  • Takeaways & Limitations

    The framework supports low-complexity, real-time recovery of latent structures in incomplete streaming data, including multi-way tensor structure.

Abstract

from arXiv · show

Extracting latent low-dimensional structure from high-dimensional data is of paramount importance in timely inference tasks encountered with `Big Data' analytics. However, increasingly noisy, heterogeneous, and incomplete datasets as well as the need for {\em real-time} processing of streaming data pose major challenges to this end. In this context, the present paper permeates benefits from rank minimization to scalable imputation of missing data, via tracking low-dimensional subspaces and unraveling latent (possibly multi-way) structure from \emph{incomplete streaming} data. For low-rank matrix data, a subspace estimator is proposed based on an exponentially-weighted least-squares criterion regularized with the nuclear norm. After recasting the non-separable nuclear norm into a form amenable to online optimization, real-time algorithms with complementary strengths are developed and their convergence is established under simplifying technical assumptions. In a stationary setting, the asymptotic estimates obtained offer the well-documented performance guarantees of the {\em batch} nuclear-norm regularized estimator. Under the same unifying framework, a novel online (adaptive) algorithm is developed to obtain multi-way decompositions of \emph{low-rank tensors} with missing entries, and perform imputation as a byproduct. Simulated tests with both synthetic as well as real Internet and cardiac magnetic resonance imagery (MRI) data confirm the efficacy of the proposed algorithms, and their superior performance relative to state-of-the-art alternatives.

I. INTRODUCTION

The paper develops scalable online methods for tracking low-dimensional subspaces and decomposing incomplete streaming matrices and tensors. It establishes convergence and stationary-setting performance guarantees, with experiments supporting effectiveness against alternatives and for tensor imputation.

  • Motivation: The paper targets low-dimensional structure extraction from noisy, heterogeneous, incomplete, and streaming high-dimensional data.Applications include images, network traffic, and movie ratings, where observations arrive sequentially and may lie in a low-dimensional subspace.
  • Matrix methods: For matrix data, it proposes online subspace tracking and signal reconstruction by viewing the task as noisy low-rank matrix completion.The estimator uses an exponentially weighted least-squares criterion regularized by the nuclear norm, recast for online optimization.
  • Theory: The framework develops real-time algorithms with complementary strengths and establishes their convergence under simplifying technical assumptions.For stationary data under mild assumptions, the online algorithms attain the global optimum of the batch nuclear-norm regularized problem.
  • Tensor methods: For incomplete streaming tensors, the paper introduces an online low-rank decomposition method that performs missing-entry imputation by reconstructing the data cube from learned factors.The tensor algorithm uses stochastic-gradient iterations and separable Frobenius-norm regularization of PARAFAC factors.
  • Evaluation: Experiments on synthetic data, Internet traffic, and cardiac MRI support the algorithms’ effectiveness and superior matrix-case performance relative to state-of-the-art alternatives.The tensor tests report imputation of up to 75% missing entries, while the methods are also intended for massive arrays that do not fit in main memory.

II. PRELIMINARIES AND PROBLEM STATEMENT

The paper models noisy, incomplete streaming vectors as signals lying in slowly varying low-dimensional subspaces, with the goals of online subspace estimation and reconstruction. It formulates scalable low-rank matrix imputation using nuclear-norm regularization and a separable factorization.

  • Problem statement: Streaming observations are noisy, incomplete vectors whose signals lie in a low-dimensional subspace that may change slowly over time.The sampling operator retains observed entries and sets unavailable entries to zero.
  • Problem statement: The online task estimates the evolving subspace and reconstructs each signal vector as a byproduct.
  • Low-rank formulation: Because the signal matrix is approximately low rank, rank minimization is replaced by the nuclear norm, the sum of singular values.
  • Challenges: The problem must address growing optimization size, costly SVD computations, and nuclear-norm nonseparability as observations arrive sequentially.
  • Separable regularization: A bilinear factorization reduces variables from Pt to ρ(P + t), which is significant when ρ is small and P and t are large.
  • Separable regularization: Separable Frobenius regularization preserves optimality relative to the nuclear-norm problem when ρ ≥ rank( X̂t), although the reformulation is nonconvex and may have non-global stationary points.

III. ONLINE RANK MINIZATION FOR MATRIX IMPUTATION

The paper develops an exponentially weighted online estimator for incomplete matrix streams, using alternating recursive least squares to track subspaces and reconstruct missing data. The design supports both finite-memory adaptation and stationary batch-equivalent behavior while controlling computational cost.

  • Online estimator: Sequentially acquired observations motivate recursively updating subspace estimates instead of recomputing them from scratch.
  • Online estimator: The exponentially weighted least-squares estimator uses a forgetting factor θ to emphasize recent measurements and track nonstationary environments.
  • Online estimator: With infinite memory, θ = 1, the online formulation coincides with the batch estimator.
  • Contribution: The paper’s novelty is subspace tracking from incomplete measurements together with online low-rank matrix and tensor completion.
  • Recursive updates: Alternating minimization updates the coefficient vector through ridge regression and the subspace rows through recursive least squares, yielding reconstruction byproduct estimates.

B. Low-complexity stochastic-gradient subspace updates

A stochastic-gradient alternative reduces the cost of updating the tracked subspace by replacing exact quadratic minimization with first-order updates, while an accelerated variant improves learning speed without changing the core online framework. These updates avoid matrix inversions but trade computation against convergence behavior.

  • Low-complexity stochastic-gradient subspace updates: The low-complexity method replaces exact quadratic subspace minimization with stochastic-gradient iterations to reduce computational complexity.
  • Low-complexity stochastic-gradient subspace updates: The stochastic-gradient update uses the instantaneous gradient of the incomplete-data loss with a step-size rule based on quadratic majorization.
  • Low-complexity stochastic-gradient subspace updates: Unlike the recursive least-squares algorithm, the stochastic-gradient subspace update requires no matrix inversions.
  • Acceleration: Nesterov-style extrapolation accelerates the online stochastic-gradient updates without increasing their per-iteration subspace-update order.
  • Acceleration: The accelerated method has convergence rate no worse than O(1/k^2) in the cited batch-gradient analysis.
  • Computational trade-off: The standard stochastic-gradient algorithm costs O(|ωt|ρ^2), while acceleration adds O(Pρ) for subspace extrapolation.

IV. PERFORMANCE GUARANTEES

The online algorithms are analyzed under technical assumptions, with convergence established for first-order updates and related guarantees for the second-order method. In stationary settings, the subspace iterates asymptotically approach stationary points of the corresponding batch problem.

  • Assumptions: The analysis assumes infinite memory, compact iterates, statistically independent observations, bounded data, and a bounded underlying subspace.Independence is acknowledged as potentially violated by temporal correlation, while boundedness and subspace assumptions support tractable analysis.
  • First-order algorithm: The first-order algorithm converges almost surely to stationary points of the batch problem under (A1)–(A3), fixed λ, and a positive Hessian lower bound.The result is stated for Algorithm 1 with θ = 1.
  • Computational trade-offs: The finite-time approximate cost is computationally preferable because direct minimization of the growing target cost becomes increasingly complex.Each update uses the previous subspace estimate to form a smooth quadratic approximation.
  • Convergence argument: The approximate cost asymptotically matches the target cost, and their gradient difference vanishes as time increases.The proof uses tight upper-bound surrogates, quasi-martingale convergence, and regularity conditions.
  • SGD convergence: The SGD iterates converge under stated step-size and regularity conditions, asymptotically coinciding with stationary points of the batch problem.The proposition concerns fixed λ and requires a lower bound involving α_t and the observed-data curvature term.
  • Accelerated variant: Convergence of the accelerated variant is not established because an appropriate surrogate whose minimizer matches the extrapolated update remains unclear.The paper notes that alternative proof techniques may help formalize this result.

C. Optimality

The section asks whether asymptotic online subspace estimates yield an optimal solution of the batch nuclear-norm problem. A positive answer is established under a subsequence optimality condition, with numerical evidence indicating rapid attainment of batch performance.

  • Optimality: The central question is whether the reconstructed estimate from learned subspaces becomes an optimal solution of the batch problem as t →∞.This requires comparing the asymptotic optimality conditions of the online and batch formulations.
  • Optimality: A positive answer is established for subspace iterates generated by the proposed algorithms.The result is formalized in the next proposition and supplemented by numerical tests.
  • Numerical implication: The online method’s performance is numerically indicated to reach that of the batch estimator after a modest number of iterations.This evidence is reported for Algorithm 1.
  • Optimality: If a subsequence satisfies the stated gradient condition, its iterates satisfy the optimality conditions for the batch problem almost surely.The condition is discussed for both time-invariant and numerically observed time-varying regularization parameters.
  • Motivation: The tensor setting motivates the same question because streaming, incomplete multi-way data require low-complexity real-time latent-structure extraction.Examples include dynamic networks, EEG recordings, and sparse-sampled NMR data.

A. Low-rank tensors and the PARAFAC decomposition

The paper models incomplete streaming tensors with low-rank PARAFAC decompositions, using factor matrices to represent latent structure and support imputation. An adaptive online formulation extends batch tensor completion to sequentially arriving slices.

  • PARAFAC model: PARAFAC represents a three-way tensor as a sum of R rank-one outer products, with each slice expressed using shared factor matrices.The factor matrices A, B, and C provide the mode-wise components of the decomposition.
  • PARAFAC model: PARAFAC is useful for latent-structure analysis, but tensor rank determination is NP-hard and exact identifiability requires technical conditions.Under those conditions, factors are unique up to common column permutation and scaling.
  • Tensor completion: Low-dimensional PARAFAC structure couples observed and missing entries, reducing effective degrees of freedom for imputation.A rough recoverability condition compares available samples with the R(M + N + T) unknown factor parameters.
  • Tensor completion: pm ≤ 1 − R(M + N + T)/(MNT) is a rough bound under which the tensor may potentially be recovered from incomplete entries.This follows from comparing available samples with the number of factor unknowns.
  • Streaming algorithm: The proposed method offers an online approach for decomposing and imputing low-rank streaming tensors as incomplete slices arrive sequentially.It extends the batch formulation to adaptive factorization on the fly.
  • Regularization: The regularizer encourages controllable tensor rank through λ, without requiring the true rank when an upper bound is supplied.The upper bound must be paired with appropriate tuning of λ.
  • Convergence: Under convergence conditions, tensor subspace iterates asymptotically coincide with stationary points of the batch tensor-completion problem.The online decomposition can therefore be formed after learning the tensor subspace in a stationary setting.

VI. NUMERICAL TESTS

The numerical section evaluates the proposed first- and second-order online algorithms using both synthetic and real datasets.

  • Experimental design: The experiments assess the convergence and effectiveness of the proposed algorithms through computer simulations.Both synthetic and real data tests are included.

A. Synthetic matrix data tests

Synthetic matrix experiments show Algorithm 1 approaches the batch nuclear-norm objective, remains accurate under missing data, and is more stable than competing trackers when misses are substantial. Its trade-off is higher per-iteration complexity.

  • Synthetic matrix data tests: Algorithm 1’s average cost converges to the optimal objective of the batch estimator.
  • Synthetic matrix data tests: Algorithm 1 attains better estimation accuracy than PETRELS and GROUSE when all use the same subspace dimension.
  • Synthetic matrix data tests: 75% missing observations produce erratic PETRELS behavior when rank is overestimated, while GROUSE and PETRELS become numerically unstable under many misses.
  • Synthetic matrix data tests: Ridge regularization renders Algorithm 1 numerically stable, but its per-iteration computational complexity is higher.

C. Synthetic tensor data tests

Synthetic tensor experiments evaluate online decomposition and imputation under severe missingness, showing geometric error reduction and scalable computation. The approach also reconstructs cardiac MRI images from sparse observations.

  • Synthetic tensor data tests: After sufficient data arrive, tensor estimation error decreases geometrically and approaches a σ2-neighborhood of the ground-truth slice.
  • Synthetic tensor data tests: Algorithm 3 accurately reconstructs large tensor slices, supporting linear convergence of the estimator.
  • Synthetic tensor data tests: Smaller π values reduce runtime because fewer observed entries require fewer computations per iteration.
  • Real tensor data tests: The tensor formulation also supports online network monitoring, where significant anomalies are correctly detected in real time.

VII. CONCLUDING SUMMARY

The paper develops online subspace tracking and tensor decomposition methods for incomplete streaming data. The methods attain batch-estimator guarantees for stationary matrices and impute tensors with up to 75% missing entries.

  • VII. CONCLUDING SUMMARY: The paper develops scalable online algorithms for highly incomplete multi-way Big Data arrays.
  • VII. CONCLUDING SUMMARY: For low-rank matrices, an EWLS nuclear-norm-regularized subspace tracker is developed with first- and second-order variants.
  • VII. CONCLUDING SUMMARY: In stationary settings, the proposed matrix algorithms asymptotically converge and offer the performance guarantees of the batch estimator.
  • VII. CONCLUDING SUMMARY: The online tensor algorithm decomposes low-rank tensors with missing entries and imputes cardiac MRI images with up to 75% missing entries.
  • VII. CONCLUDING SUMMARY: Open questions include convergence analysis for accelerated SGD, spatiotemporal statistical modeling, and relaxing qualification constraints in dynamic environments.

APPENDIX

The appendix establishes optimality connections for the matrix and tensor formulations using asymptotic stationarity and primal-dual conditions. The proofs rely on boundedness, qualification constraints, and equivalent smooth formulations.

  • APPENDIX: The proof for the matrix estimator starts from asymptotic stationarity and verifies optimality conditions for the nuclear-norm problem.
  • APPENDIX: An equivalent formulation removes the non-smooth nuclear norm, enabling the proof to analyze the limiting iterates.
  • APPENDIX: The tensor proof uses a Lagrangian with dual variables associated with the positive-semidefiniteness constraint.
  • APPENDIX: Primal feasibility, dual feasibility, complementary slackness, and subgradient conditions together establish the required optimality result.
  • APPENDIX: Boundedness and the qualification constraint support convergence of the complementary-slackness term to zero.
Loading 1404.4667v1…