This paper examines the existence of efficiently implementable approximations of a general real linear dimensionality reduction (LDR) operator. The specific focus is on approximating a given LDR operator with a partial circulant structured matrix (a matrix whose rows are related by circular shifts) as these constructions allow for low-memory footprint and computationally efficient implementations. Our main contributions are theoretical: we quantify how well general matrices may be approximated (in a Frobenius sense) by partial circulant structured matrices, and also consider a variation of this problem where the aim is only to accurately approximate the action of a given LDR operator on a restricted set of inputs. For the latter setting, we also propose a sparsity-regularized alternating minimization based algorithm for learning partial circulant approximations from data, and provide experimental evidence demonstrating the potential efficacy of this approach on real-world data.
|Original language||English (US)|
|Title of host publication||2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - Proceedings|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||5|
|State||Published - Jun 16 2017|
|Event||2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017 - New Orleans, United States|
Duration: Mar 5 2017 → Mar 9 2017
|Name||ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings|
|Other||2017 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2017|
|Period||3/5/17 → 3/9/17|
Bibliographical noteFunding Information:
This work was supported in part by DARPA/ONR Grant No. N66001-11-1-4090 and the DARPA Young Faculty Award, Grant No. N66001-14-1-4047.
© 2017 IEEE.
Copyright 2017 Elsevier B.V., All rights reserved.
- Circulant matrices
- big data
- matrix factorization
- sparse regularization
- subspace learning