Yuejie Chi

Signal Processing under Geometric Constraints

One major challenge in the data deluge is identifying patterns of activity from the flow of information in a network, examples including sensor networks, social networks and biological networks, by the prospect of systematically learning and predicting the network behavior. Network inference is hard because of its massive scale and time dynamics of the flow of information. How can we reduce network dimensionality without compromising the potential for learning and control within limited processing capabilities?

What saves the day is the geometry of information flow, the fact that it can be viewed as a low-dimensional manifold in a very high dimensional space. Leveraging low-dimensional data representations through geometric constraints such as low rank, sparsity, and graphs, we hope to reduce the sampling cost of information acquisition and improve the performance of decision making. However there is still the problem of tapping into that manifold. When the manifold is linear, we developed online algorithms with low-complexity that can estimate and track the evolution of a low-rank subspace from partial observations even with Poisson noise, and demonstrated superior performance on various applications. What is truly exciting is the recognition that the geometry of information flow, expressed in terms of the top principal components of the data covariance matrix, is preserved even from highly incomplete observations.

In order to further overcome the barrier between the high data generation rate and limited processing capabilities facing many modern data-intensive applications, we realized that by leveraging structural assumptions of covariance structures, a single sketch per sample suffices for accurately reconstructing the covariance matrix rather than the original data set. This offers a radical breakthrough for learning covariance structures requiring substantially fewer storage of the data than conventional methods. The key approach is to develop efficient sketching strategies of streaming data tailored to specific inference tasks with a recognition of the embedded low-dimensional structures. This idea can be extended to sketch and analyze graph-structured data, as well as detect anomalies and change-points. Our new framework has the potential to advance the paradigm of high-dimensional data analysis from simple post-processing toward an integration of data priors, agile acquisition, and adaptive processing.

Overview

• Streaming PCA and Subspace Tracking: The Missing Data Case [Arxiv] [Code]
  L. Balzano, Y. Chi and Y. M. Lu, Proceedings of the IEEE, vol. 106, no. 8, pp. 1293-1310, 2018.

• Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation [Arxiv]
  Y. Chen and Y. Chi, IEEE Signal Processing Magazine, vol. 35, no. 4, pp. 14-31, 2018.

Covariance Sketching and Low-Rank Covariance Estimation

• Subspace Estimation from Unbalanced and Incomplete Data Matrices: $\ell_{2,\infty}$ Statistical Guarantees [Main] [Arxiv]
  C. Cai, G. Li, Y. Chi, H. V. Poor, and Y. Chen, The Annals of Statistics, vol. 49, no. 2, pp. 944-967, 2021.

• Nonconvex Matrix Factorization from Rank-One Measurements [Arxiv]
  Y. Li, C. Ma, Y. Chen, and Y. Chi, IEEE Trans. on Information Theory, vol. 67, no. 3, pp. 1928-1950, 2021. Short version at AISTATS 2019.

• Low-Rank Structured Covariance Matrix Estimation
  A. P. Shikhaliev, L. C. Potter and Y. Chi, IEEE Signal Processing Letters, vol. 26, no. 5, pp. 700-704, 2019.

• Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
  Y. Li, Y. Sun and Y. Chi, IEEE Trans. on Signal Processing, vol. 65, no. 2, pp. 397-408, 2017.

• Subspace Learning From Bits
  Y. Chi and H. Fu, IEEE Trans. on Signal Processing, vol. 65, no. 17, pp. 4429-4442, 2017.

• Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming [Arxiv]
  Y. Chen, Y. Chi and A. J. Goldsmith. IEEE Trans. on Information Theory, vol. 61, pp. 4034 - 4059, 2015.

• Kronecker Covariance Sketching for Spatial-Temporal Data [Invited Paper]
  Y. Chi. European Signal Processing Conference (EUSIPCO), 2016.

Subspace Tracking and Statistical Inference for Streaming Data

• PETRELS: Parallel Subspace Estimation and Tracking using Recursive Least Squares from Partial Observations [Code]
  Y. Chi, Y. C. Eldar, and R. Calderbank. IEEE Trans. on Signal Processing, vol. 61, pp. 5947 - 5959, 2013.
  Short version received Best Student Paper Award at ICASSP 2012.

• Stochastic Approximation and Memory-Limited Subspace Tracking for Poisson Streaming Data [PDF]
  L. Wang and Y. Chi, IEEE Trans. on Signal Processing, vol. 66, no. 4, pp. 1051-1064, 2018.

• Shift-Invariant Subspace Tracking with Missing Data [Invited Paper]
  M. Cho and Y. Chi, International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2019.

• Change-Point Estimation of High-Dimensional Streaming Data via Sketching
  Y. Chi and Y. Wu. Asilomar Conference on Signals, Systems, and Computers (Asilomar), 2015.

Leveraging Graph Structures for Better Inference

• Privacy-Preserving Federated Multi-task Linear Regression: A One-Shot Linear Mixing Approach Inspired by Graph Regularization [PDF]
  H. Lee, A. Bertozzi, J. Kovacevic, and Y. Chi, International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2022.

• Learning Latent Features with Pairwise Penalties in Matrix Completion
  K. Ji, J. Tan, J. Xu, and Y. Chi, IEEE Trans. on Signal Processing, vol. 68, pp. 4210-4225, 2020.

• Vector-Valued Graph Trend Filtering with Non-Convex Penalties [Arxiv] [Code]
  R. Varma*, H. Lee*, J. Kovacevic and Y. Chi, IEEE Trans. on Signal Processing over Networks, vol. 6, no. 1, pp. 48-62, 2020. (*=equal contribution)

Sparsity for Signal Processing and Machine Learning

• Blind Calibration of Multi-Channel Samplers using Sparse Recovery [Invited Paper]
  Y. Li, Y. He, Y. Chi and Y. M. Lu. IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), 2015.

• Classification and Boosting with Multiple Collaborative Representations
  Y. Chi and F. Porikli. IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 36, pp. 1519 - 1531, 2014.

• Knowledge-Enhanced Matching Pursuit
  Y. Chi and R. Calderbank. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2013.