Recovery of Sparse Matrices via Matrix Sketching

Abstract

In this paper, we consider the problem of recovering an unknown sparse matrix X from the matrix sketch Y = AX B^T. The dimension of Y is less than that of X, and A and B are known matrices. This problem can be solved using standard compressive sensing (CS) theory after converting it to vector form using the Kronecker operation. In this case, the measurement matrix assumes a Kronecker product structure. However, as the matrix dimension increases the associated computational complexity makes its use prohibitive. We extend two algorithms, fast iterative shrinkage threshold algorithm (FISTA) and orthogonal matching pursuit (OMP) to solve this problem in matrix form without employing the Kronecker product. While both FISTA and OMP with matrix inputs are shown to be equivalent in performance to their vector counterparts with the Kronecker product, solving them in matrix form is shown to be computationally more efficient. We show that the computational gain achieved by FISTA with matrix inputs over its vector form is more significant compared to that achieved by OMP.

References in corpus (1)

• Sketching Sparse Matrices

Cited by in corpus (8)

• Sub-Nyquist Radar Systems: Temporal, Spectral and Spatial Compression
• Sub-Nyquist SAR via Fourier Domain Range Doppler Processing
• Compressive Sensing-Based Detection with Multimodal Dependent Data
• Unambiguous Delay-Doppler Recovery from Random Phase Coded Pulses
• Application of Compressive Sensing Techniques in Distributed Sensor Networks: A Survey
• Detecting the large entries of a sparse covariance matrix in sub-quadratic time
• Localized Compression: Applying Convolutional Neural Networks to Compressed Images
• Positive Definite Estimation of Large Covariance Matrix Using Generalized Nonconvex Penalties