Sparsity-Exploiting Distributed Projections onto a Simplex

References

• Amdahl GM (1967) Validity of the single processor approach to achieving large scale computing capabilities. Proc. April 18–20, 1967, Spring Joint Comput. Conf. (Association for Computing Machinery, New York), 483–485.Google Scholar
• Barlaud M, Belhajali W, Combettes PL, Fillatre L (2017) Classification and regression using an outer approximation projection-gradient method. IEEE Trans. Signal Processing 65(17):4635–4644.Crossref, Google Scholar
• Barman S, Liu X, Draper SC, Recht B (2013) Decomposition methods for large scale LP decoding. IEEE Trans. Inform. Theory 59(12):7870–7886.Crossref, Google Scholar
• Bentley JL, McIlroy MD (1993) Engineering a sort function. Software Practice Experience 23(11):1249–1256.Crossref, Google Scholar
• Bioucas-Dias JM, Plaza A, Dobigeon N, Parente M, Du Q, Gader P, Chanussot J (2012) Hyperspectral unmixing overview: Geometrical, statistical, and sparse regression-based approaches. IEEE J. Selected Topics Appl. Earth Observations Remote Sensing 5(2):354–379.Crossref, Google Scholar
• Blondel M, Fujino A, Ueda N (2014) Large-scale multiclass support vector machine training via Euclidean projection onto the simplex. 2014 22nd Internat. Conf. Pattern Recognition (IEEE, Piscataway, NJ), 1289–1294.Google Scholar
• Blum M, Floyd RW, Pratt VR, Rivest RL, Tarjan RE (1973) Time bounds for selection. J. Comput. System Sci. 7(4):448–461.Crossref, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Brodie J, Daubechies I, De Mol C, Giannone D, Loris I (2009) Sparse and stable Markowitz portfolios. Proc. Natl. Acad. Sci. USA 106(30):12267–12272.Crossref, Google Scholar
• Candès EJ, Wakin MB, Boyd SP (2008) Enhancing sparsity by reweighted ℓ1 minimization. J. Fourier Anal. Appl. 14:877–905.Crossref, Google Scholar
• Chang CC, Lin CJ (2011) LIBSVM: A library for support vector machines. ACM Trans. Intelligent Systems Tech. 2(3):1–27.Crossref, Google Scholar
• Chartrand R, Yin W (2008) Iteratively reweighted algorithms for compressive sensing. 2008 IEEE Internat. Conf. Acoustics Speech Signal Processing (IEEE, Piscataway, NJ), 3869–3872.Google Scholar
• Chen X, Zhou W (2014) Convergence of the reweighted ℓ1 minimization algorithm for ℓ2-ℓp minimization. Comput. Optim. Appl. 59(1–2):47–61.Crossref, Google Scholar
• Chen SS, Donoho DL, Saunders MA (1998) Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1):33–61.Crossref, Google Scholar
• Cominetti RM, Mascarenhas WF, Silva PJS (2014) A Newton’s method for the continuous quadratic knapsack problem. Math. Programming Comput. 6:151–196.Crossref, Google Scholar
• Condat L (2016) Fast projection onto the simplex and the ℓ1 ball. Math. Programming Ser. A 158(1):575–585.Crossref, Google Scholar
• Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to Algorithms, 3rd ed. (MIT Press, Cambridge, MA).Google Scholar
• Dai Y, Chen C (2023) Sparsity-exploiting distributed projections onto a simplex. https://dx.doi.org/10.1287/ijoc.2022.0328.cd, https://github.com/INFORMSJoC/2022.0328.Google Scholar
• Dai Y, Fletcher R (2006) New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math. Programming 106:403–421.Crossref, Google Scholar
• Donoho DL, Elad M (2003) Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization. Proc. Natl. Acad. Sci. USA 100(5):2197–2202.Crossref, Google Scholar
• Duchi J, Shalev-Shwartz S, Singer Y, Chandra T (2008) Efficient projections onto the ℓ1-ball for learning in high dimensions. Proc. 25th Internat. Conf. Machine Learn. (Association for Computing Machinery, New York), 272–279.Google Scholar
• Greb A, Zachmann G (2006) GPU-ABiSort: Optimal parallel sorting on stream architectures. Proc. 20th IEEE Internat. Parallel Distributed Processing Sympos. (IEEE, Piscataway, NJ).Google Scholar
• Held M, Wolfe P, Crowder HP (1974) Validation of subgradient optimization. Math. Programming 6:62–88.Crossref, Google Scholar
• Iutzeler F, Condat L (2018) Distributed projection on the simplex and ℓ1 ball via ADMM and gossip. IEEE Signal Processing Lett. 25(11):1650–1654.Crossref, Google Scholar
• Kiwiel KC (2008) Breakpoint searching algorithms for the continuous quadratic knapsack problem. Math. Programming 112:473–491.Crossref, Google Scholar
• Ladner RE, Fischer MJ (1980) Parallel prefix computation. J. ACM 27(4):831–838.Crossref, Google Scholar
• Lellmann J, Kappes J, Yuan J, Becker F, Schnörr C (2009) Convex multi-class image labeling by simplex-constrained total variation. Tai XC, Mørken K, Lysaker M, Lie KA, eds. Scale Space and Variational Methods in Computer Vision (SSVM), Lecture Notes in Computer Science, vol. 5567 (Springer, Berlin, Heidelberg), 150–162.Crossref, Google Scholar
• Liu X, Draper SC (2016) The ADMM penalized decoder for LDPC codes. IEEE Trans. Inform. Theory 62(6):2966–2984.Crossref, Google Scholar
• Mahmoud HM (2000) Sorting: A Distribution Theory, vol. 54 (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Michelot C (1986) A finite algorithm for finding the projection of a point onto the canonical simplex of Rn. J. Optim. Theory Appl. 50:195–200.Crossref, Google Scholar
• Ohio Supercomputer Center (1987) Ohio Supercomputer Center. Accessed July 15, 2023, http://osc.edu/ark:/19495/f5s1ph73.Google Scholar
• Perez G, Ament S, Gomes CP, Barlaud M (2020) Efficient projection algorithms onto the weighted ℓ1 ball. Preprint, submitted September 7, https://arxiv.org/abs/2009.02980.Google Scholar
• Robinson AG, Jiang N, Lerme CS (1992) On the continuous quadratic knapsack problem. Math. Programming 55:99–108.Crossref, Google Scholar
• Tibshirani R (1996) Regression shrinkage and selection via the lasso. J. Roy. Statist. Soc. B 58(1):267–288.Crossref, Google Scholar
• Tibshirani R (1997) The LASSO method for variable selection in the Cox model. Statist. Medicine 16(4):385–395.Crossref, Google Scholar
• van den Berg E (2020) A hybrid quasi-Newton projected-gradient method with application to LASSO and basis-pursuit denoising. Math. Programming Comput. 12:1–38.Crossref, Google Scholar
• van den Berg E, Friedlander MP (2009) Probing the pareto frontier for basis pursuit solutions. SIAM J. Sci. Comput. 31(2):890–912.Crossref, Google Scholar
• Wang S, Bai Y, Pekhimenko G (2020) BPPSA: Scaling back-propagation by parallel scan algorithm. Preprint, submitted May 7, https://arxiv.org/abs/1907.10134.Google Scholar
• Wang G, Yu W, Liang X, Wu Y, Yu B (2022) An iterative reduction FISTA algorithm for large-scale LASSO. SIAM J. Sci. Comput. 44(4):A1989–A2017.Crossref, Google Scholar
• Wasson M, Milicevic M, Draper SC, Gulak G (2019) Hardware-based linear program decoding with the alternating direction method of multipliers. IEEE Trans. Signal Processing 67(19):4976–4991.Crossref, Google Scholar
• Wei H, Jiao X, Mu J (2015) Reduced-complexity linear programming decoding based on ADMM for LDPC codes. IEEE Comm. Lett. 19(6):909–912.Crossref, Google Scholar
• Xavier C, Iyengar SS (1998) Introduction to Parallel Algorithms, vol. 1 (John Wiley & Sons, Hoboken, NJ).Google Scholar
• Zhang X, Siegel PH (2013) Efficient iterative LP decoding of LDPC codes with alternating direction method of multipliers. 2013 IEEE Internat. Sympos. Inform. Theory (IEEE, Piscataway, NJ), 1501–1505.Google Scholar
• Zhang G, Heusdens R, Kleijn WB (2013) Large scale LP decoding with low complexity. IEEE Comm. Lett. 17(11):2152–2155.Crossref, Google Scholar
• Zhang A, Lipton ZC, Li M, Smola AJ (2021) Dive into deep learning. Preprint, submitted June 21, https://arxiv.org/abs/2106.11342.Google Scholar