2014

Approximate Matrix Multiplication with Application to Linear Embeddings

Kyrillidis, Anastasios, Vlachos, Michail, Zouzias, Anastasios

Understand

In this paper, we study the problem of approximately computing the product of two real matrices.

In particular, we analyze a dimensionality-reduction-based approximation algorithm due to Sarlos [1], introducing the notion of nuclear rank as the ratio of the nuclear norm over the spectral norm.
The presented bound has improved dependence with respect to the approximation error (as compared to previous approaches), whereas the subspace -- on which we project the input matrices -- has dimensions proportional to the maximum of their nuclear rank and it is independent of the input dimensions.
In addition, we provide an application of this result to linear low-dimensional embeddings.

Built on

W. B. Johnson and J. Lindenstrauss, “Extensions of lipschitz mappings into a hilbert space,” Contemporary mathematics , vol. 26, no. 189-206, p. 1, 1984
1984
Earlier work this paper cites.
P. Indyk and R. Motwani, “Approximate nearest neighbors: towards removing the curse of dimensionality,” in Proceedings of the thirtieth annual ACM symposium on Theory of computing . ACM, 1998, pp. 604–613
1998
Earlier work this paper cites.
B. Klartag and S. Mendelson, “Empirical processes and random projections,” Journal of Functional Analysis , vol. 225, no. 1, pp. 229 – 245, 2005. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0022123604003635
2005
Earlier work this paper cites.
T. Sarlos, “Improved approximation algorithms for large matrices via random projections,” in Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on . IEEE, 2006, pp. 143–152
2006
Earlier work this paper cites.
S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann, “Reconstruction and subgaussian operators in asymptotic geometric analysis,” Geometric and Functional Analysis , vol. 17, no. 4, pp. 1248–1282, 2007. [Online]. Available: http://dx.doi.org/10.1007/s00039-007-0618-7
2007
Earlier work this paper cites.
P. K. Agarwal, S. Har-Peled, and H. Yu, “Embeddings of surfaces, curves, and moving points in euclidean space,” in Proceedings of the Twenty-third Annual Symposium on Computational Geometry , ser. SCG ’07. New York, NY, USA: ACM, 2007, pp. 381–389. [Online]. Available: http://doi.acm.org/10.1145/1247069.1247135
2007
Earlier work this paper cites.
P. Indyk and A. Naor, “Nearest-neighbor-preserving embeddings,” ACM Trans. Algorithms , vol. 3, no. 3, Aug. 2007. [Online]. Available: http://doi.acm.org/10.1145/1273340.1273347
2007
Earlier work this paper cites.

Similar

K. L. Clarkson, “Tighter bounds for random projections of manifolds,” in Proceedings of the twenty-fourth annual symposium on Computational geometry . ACM, 2008, pp. 39–48
2008
Cited alongside, same era.
M. W. Mahoney and P. Drineas, “Cur matrix decompositions for improved data analysis,” Proceedings of the National Academy of Sciences , vol. 106, no. 3, pp. 697–702, 2009
2009
Cited alongside, same era.
C. Boutsidis, M. W. Mahoney, and P. Drineas, “An improved approximation algorithm for the column subset selection problem,” in SODA , 2009, pp. 968–977
2009
Cited alongside, same era.
R. G. Baraniuk and M. B. Wakin, “Random projections of smooth manifolds,” Foundations of Computational Mathematics , vol. 9, no. 1, pp. 51–77, 2009. [Online]. Available: http://dx.doi.org/10.1007/s10208-007-9011-z
2009
Cited alongside, same era.
C. Boutsidis, A. Zouzias, and P. Drineas, “Random projections for $k$-means clustering,” in NIPS , 2010, pp. 298–306
2010
Cited alongside, same era.
A. Magen and A. Zouzias, “Low rank matrix-valued chernoff bounds and approximate matrix multiplication,” in SODA , 2011, pp. 1422–1436
2011
Cited alongside, same era.
Y. Bartal, B. Recht, and L. J. Schulman, “Dimensionality reduction: Beyond the johnson-lindenstrauss bound,” in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , ser. SODA ’11. SIAM, 2011, pp. 868–887. [Online]. Available: http://dl.acm.org/citation.cfm?id=2133036.2133104
2011
Cited alongside, same era.

Then

L.-A. Gottlieb and R. Krauthgamer, “A nonlinear approach to dimension reduction,” in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms , ser. SODA ’11. SIAM, 2011, pp. 888–899. [Online]. Available: http://dl.acm.org/citation.cfm?id=2133036.2133105
2011
Later among the works it cites.
C. Hegde, A. Sankaranarayanan, W. Yin, and R. Baraniuk, “A convex approach for learning near-isometric linear embeddings,” preparation, August , 2012
2012
Later among the works it cites.
V. Chandrasekaran and M. I. Jordan, “Computational and statistical tradeoffs via convex relaxation,” Proceedings of the National Academy of Sciences , vol. 110, no. 13, pp. E1181–E1190, 2013
2013
Later among the works it cites.
D. Achlioptas, Z. Karnin, and E. Liberty, “Near-optimal entrywise sampling for data matrices,” arXiv preprint arXiv:1311.4643 , 2013
Original
2013
Later among the works it cites.
A. Zouzias, “Randomized primitives for linear algebra and applications,” Ph.D. dissertation, University of Toronto, 2013
2013
Later among the works it cites.
E. Grant, C. Hegde, and P. Indyk, “Nearly optimal linear embeddings into very low dimensions,” IEEE GlobalSIP Symposium on Sensing and Statistical Inference, Austin, TX , 2013
2013
Later among the works it cites.
M. Rudelson and R. Vershynin, “Hanson-wright inequality and sub-gaussian concentration,” Electron. Commun. Probab. , vol. 18, pp. no. 82, 1–9, 2013
2013
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…