In-network Sparsity-regularized Rank Minimization: Algorithms and Applications

Abstract

Given a limited number of entries from the superposition of a low-rank matrix plus the product of a known fat compression matrix times a sparse matrix, recovery of the low-rank and sparse components is a fundamental task subsuming compressed sensing, matrix completion, and principal components pursuit. This paper develops algorithms for distributed sparsity-regularized rank minimization over networks, when the nuclear- and ${\ell }_1$-norm are used as surrogates to the rank and nonzero entry counts of the sought matrices, respectively. While nuclear-norm minimization has well-documented merits when centralized processing is viable, non-separability of the singular-value sum challenges its distributed minimization. To overcome this limitation, an alternative characterization of the nuclear norm is adopted which leads to a separable, yet non-convex cost minimized via the alternating-direction method of multipliers. The novel distributed iterations entail reduced-complexity per-node tasks, and affordable message passing among single-hop neighbors. Interestingly, upon convergence the distributed (non-convex) estimator provably attains the global optimum of its centralized counterpart, regardless of initialization. Several application domains are outlined to highlight the generality and impact of the proposed framework. These include unveiling traffic anomalies in backbone networks, predicting networkwide path latencies, and mapping the RF ambiance using wireless cognitive radios. Simulations with synthetic and real network data corroborate the convergence of the novel distributed algorithm, and its centralized performance guarantees.

30 pages, submitted for publication on the IEEE Trans. Signal Process

References in corpus (5)

• A New Approach to Collaborative Filtering: Operator Estimation with Spectral Regularization
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• Distributed Recursive Least-Squares: Stability and Performance Analysis
• A Sparsity-Aware Adaptive Algorithm for Distributed Learning
• Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies

Cited by in corpus (14)

• Signal Recovery on Graphs: Variation Minimization
• Subspace Learning and Imputation for Streaming Big Data Matrices and Tensors
• Dynamic Anomalography: Tracking Network Anomalies via Sparsity and Low Rank
• Robust PCA as Bilinear Decomposition with Outlier-Sparsity Regularization
• Recovery of Low-Rank Plus Compressed Sparse Matrices with Application to Unveiling Traffic Anomalies
• Rank regularization and Bayesian inference for tensor completion and extrapolation
• Inexact Block Coordinate Descent Algorithms for Nonsmooth Nonconvex Optimization
• Subspace-Orbit Randomized Decomposition for Low-rank Matrix Approximation
• Load curve data cleansing and imputation via sparsity and low rank
• Successive Convex Approximation Algorithms for Sparse Signal Estimation with Nonconvex Regularizations
• Joint community and anomaly tracking in dynamic networks
• Electricity Market Forecasting via Low-Rank Multi-Kernel Learning
• Designing Asymmetric Shift Operators for Decentralized Subspace Projection
• Per-Block-Convex Data Modeling by Accelerated Stochastic Approximation