Random Projections for Linear Programming

References

• Achlioptas D (2003) Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. System Sci. 66(4):671–687.Crossref, Google Scholar
• Allen-Zhu Z, Gelashvili R, Micali S, Shavit N (2014) Sparse sign-consistent Johnson-Lindenstrauss matrices: Compression with neuroscience-based constraints. Proc. Natl. Acad. Sci. 111(47):16872–16876.Crossref, Google Scholar
• Anthony M, Biggs N (1992) Computational Learning Theory: An Introduction, Cambridge Tracts in Theoretical Computer Science (Cambrige University Press, Cambridge).Google Scholar
• Bezanson J, Edelman A, Karpinski S, Shah V (2017) Julia: A fresh approach to numerical computing. SIAM Rev. 59(1):65–98.Crossref, Google Scholar
• Borgwardt K (1987) The Simplex Method: A Probabilistic Analysis (Springer, Berlin).Crossref, Google Scholar
• Boutsidis C, Zouzias A, Drineas P (2010) Random projections for k-means clustering. Advances in Neural Information Processing Systems (NIPS Foundation, La Jolla, CA), 298–306.Google Scholar
• Candès E, Tao T (2005) Decoding by Linear Programming. IEEE Trans. Inform. Theory 51(12):4203–4215.Crossref, Google Scholar
• Candès E, Tao T (2008) Reflections on compressed sensing. IEEE Inform. Theory Soc. Newsletter 58(4):14–17.Google Scholar
• Dantzig G (1990) The Diet Problem. Interfaces 20(4):43–47.Link, Google Scholar
• Dasgupta A, Kumar R, Sarlós T (2010) A sparse Johnson-Lindenstrauss transform. Schulman LJ, ed. Proc. 42nd ACM Sympos. Theory Comput., STOC ’10 (ACM, New York).Google Scholar
• Dasgupta S, Gupta A (2002) An elementary proof of a theorem by Johnson and Lindenstrauss. Random Structures and Algorithms 22(1):60–65.Crossref, Google Scholar
• de Farias DP, Roy BV (2004) On constraint sampling in the Linear Programming approach to approximate Dynamic Programming. Math. Oper. Res. 29(3):462–478.Link, Google Scholar
• IBM (2014) ILOG CPLEX 12.6 User’s Manual (IBM).Google Scholar
• Indyk P, Naor A (2007) Nearest neighbor preserving embeddings. ACM Trans. Algorithms 3(3):Article 31.Crossref, Google Scholar
• Johnson W, Lindenstrauss J (1984) Extensions of Lipschitz mappings into a Hilbert space. Hedlund G, ed., Conf. Modern Anal. Probab., Vol. 26 of Contemporary Mathematics (American Mathematical Society, Providence, RI), 189–206.Google Scholar
• Kane D, Nelson J (2014) Sparser Johnson-Lindenstrauss transforms. J. ACM 61(1):Article 4.Crossref, Google Scholar
• Koenker R (2005) Quantile Regression (Cambridge University Press, New York).Crossref, Google Scholar
• Lubin M, Dunning I (2015) Computing in operations research using julia. INFORMS J. Comput. 27(2):238–248.Link, Google Scholar
• Matoušek J (2008) On variants of the Johnson-Lindenstrauss lemma. Random Structures and Algorithms 33(2):142–156.Crossref, Google Scholar
• Matoušek J (2013) Lecture notes on metric embeddings. Technical report, ETH Zürich.Google Scholar
• Matoušek J, Gärtner B (2007) Understanding and Using Linear Programming (Springer, Berlin).Google Scholar
• Natarajan B (1995) Sparse approximate solutions to linear systems. SIAM J. Comput. 24(2):227–234.Crossref, Google Scholar
• NetLib (2015) LP instance library. http://www.netlib.org/lp/.Google Scholar
• Pan V (1985) On the complexity of a pivot step of the revised simplex algorithm. Comput. Math. with Appl. 11(11):1127–1140.Crossref, Google Scholar
• Pilanci M, Wainwright M (2014) Randomized sketches of convex programs with sharp guarantees. Internat. Sympos. Inform. Theory, ISIT IEEE, Piscataway, NJ, 921–925.Google Scholar
• Potra F, Wright S (2000) Interior-point methods. J. Computational Appl. Math. 124(1–2):281–302.Crossref, Google Scholar
• Venkatasubramanian S, Wang Q (2011) The Johnson-Lindenstrauss transform: An empirical study. Müller-Hannermann M, Werneck R, eds. Proc. 13th Workshop Algorithm Engrg. Experiments, ALENEX ’11 (SIAM, Philadelphia), 164–173.Google Scholar
• Yang J, Meng X, Mahoney M (2014) Quantile regression for large-scale applications. SIAM J. Scientific Comput. 36(5):S78–S110.Crossref, Google Scholar