A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis

References

• Absil PA, Mahony R, Sepulchre R (2008) Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, NJ).Google Scholar
• Bendory T, Eldar YC, Boumal N (2018) Non-convex phase retrieval from STFT measurements. IEEE Trans. Inform. Theory 64(1):467–484.Google Scholar
• Boumal N (2016) Nonconvex phase synchronization. SIAM J. Optim. 26(4):2355–2377.Google Scholar
• Boumal N, Absil PA (2011) RTRMC: A Riemannian trust-region method for low-rank matrix completion. Adv. Neural Inform. Processing Systems 24:406–414.Google Scholar
• Boumal N, Absil PA, Cartis C (2018) Global rates of convergence for nonconvex optimization on manifolds. IMA J. Numerical Anal. 39(1):1–33.Google Scholar
• Buettner F, Natarajan KN, Casale FP, Proserpio V, Scialdone A, Theis FJ, Teichmann SA, Marioni JC, Stegle O (2015) Computational analysis of cell-to-cell heterogeneity in single-cell RNA-sequencing data reveals hidden subpopulations of cells. Nature Biotechnology 33(2):155–160.Google Scholar
• Calinski T, Harabasz J (1974) A dendrite method for cluster analysis. Comm. Statist. 3(1):1–27.Google Scholar
• Charisopoulos V, Davis D, Díaz M, Drusvyatskiy D (2021) Composite optimization for robust blind deconvolution. Inform. Inference 10(2):333–396.Google Scholar
• Charisopoulos V, Chen Y, Davis D, Diaz M, Ding L, Drusvyatskiy D (2019) Low-rank matrix recovery with composite optimization: Good conditioning and rapid convergence. Foundations Comput. Math. Forthcoming.Google Scholar
• Chen S, Deng Z, Ma S, So AMC (2019) Manifold proximal point algorithms for dual principal component pursuit and orthogonal dictionary learning. Pro. 2019 Asilomar Conf. Signals Systems Comput.Google Scholar
• Chen S, Deng Z, Ma S, So AMC (2021) Manifold proximal point algorithms for dual principal component pursuit and orthogonal dictionary learning. IEEE Trans. Signal Processing 69:4759–4773.Google Scholar
• Chen S, Ma S, So AMC, Zhang T (2020a) Proximal gradient method for nonsmooth optimization over the Stiefel manifold. SIAM J. Optim. 30(1):210–239.Google Scholar
• Chen S, Ma S, Xue L, Zou H (2020b) An alternating manifold proximal gradient method for sparse principal component analysis and sparse canonical correlation analysis. INFORMS J. Optim. 2(3):192–208.Link, Google Scholar
• Cherian A, Sra S (2017) Riemannian dictionary learning and sparse coding for positive definite matrices. IEEE Trans. Neural Networks Learn. Systems 28(12):2859–2871.Google Scholar
• Chung F (1997) Spectral Graph Theory (American Mathematical Society, Providence, Rhode Island).Google Scholar
• Deng Q, Ramsköld D, Reinius B, Sandberg R (2014) Single-cell RNA-seq reveals dynamic, random monoallelic gene expression in mammalian cells. Sci. 343(6167):193–196.Google Scholar
• Drusvyatskiy D, Paquette C (2019) Efficiency of minimizing compositions of convex functions and smooth maps. Math. Programming Ser. A 178(1–2):503–558.Google Scholar
• Dua D, Graff C (2017) UCI machine learning repository. Accessed November 3, 2018, http://archive.ics.uci.edu/ml.Google Scholar
• Duchi JC, Ruan F (2018) Stochastic methods for composite and weakly convex optimization problems. SIAM J. Optim. 28(4):3229–3259.Google Scholar
• Duchi JC, Ruan F (2019) Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval. Inform. Inference 8(3):471–529.Google Scholar
• Ferreira OP, Oliveira PR (1998) Subgradient algorithm on Riemannian manifolds. J. Optim. Theory Appl. 97(1):93–104.Google Scholar
• Friedman J, Hastie T, Tibshirani R (2001) The Elements of Statistical Learning (Springer Series in Statistics, New York).Google Scholar
• Grohs P, Hosseini S (2016) ε-subgradient algorithms for locally Lipschitz functions on Riemannian manifolds. Adv. Comput. Math. 42(2):333–360.Google Scholar
• Hosseini S, Pouryayevali M (2011) Generalized gradients and characterization of epi-Lipschitz sets in Riemannian manifolds. Nonlinear Anal.: Theory, Methods & Appl. 74(12):3884–3895.Google Scholar
• Hosseini S, Uschmajew A (2017) A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM J. Optim. 27(1):173–189.Google Scholar
• Huang W, Wei K (2021a) Extending FISTA to Riemannian optimization for sparse PCA. Numerical Linear Algebra with Applications. Forthcoming.Google Scholar
• Huang W, Wei K (2021b) Riemannian proximal gradient methods. Math. Programming Forthcoming.Google Scholar
• Kiselev VY, Andrews TS, Hemberg M (2019) Challenges in unsupervised clustering of single-cell RNA-seq data. Nature Rev. Genetics 20:273–282.Google Scholar
• Lewis AS, Wright SJ (2016) A proximal method for composite minimization. Math. Programming 158(1–2):501–546.Google Scholar
• Li X, Sun D, Toh KC (2018) A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems. SIAM J. Optim. 28(1):433–458.Google Scholar
• Li X, Chen S, Deng Z, Qu Q, Zhu Z, So AMC (2021) Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods. SIAM J. Optim.31(3):1605–1634.Google Scholar
• Liu H, Yue MC, So AMC (2017) On the estimation performance and convergence rate of the generalized power method for phase synchronization. SIAM J. Optim. 27(4):2426–2446.Google Scholar
• Lu C, Yan S, Lin Z (2016) Convex sparse spectral clustering: Single-view to multi-view. IEEE Trans. Image Processing 25(6):2833–2843.Google Scholar
• Lu C, Feng J, Lin Z, Yan S (2018) Nonconvex sparse spectral clustering by alternating direction method of multipliers and its convergence analysis. 32nd AAAI Conf. Artificial Intelligence.Google Scholar
• Mifflin R (1977) Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15(6):959–972.Google Scholar
• Morgan XC, Kabakchiev B, Waldron L, Tyler AD, Tickle TL, Milgrom R, Stempak JM, et al. (2015) Associations between host gene expression, the mucosal microbiome, and clinical outcome in the pelvic pouch of patients with inflammatory bowel disease. Genome Biol. 16:67.Google Scholar
• Ng AY, Jordan MI, Weiss Y (2002) On spectral clustering: Analysis and an algorithm. Adv. Neural Inform. Processing Systems 14:849–856.Google Scholar
• Park S, Zhao H (2018) Spectral clustering based on learning similarity matrix. Bioinformatics 34(12):2069–2076.Google Scholar
• Pollen AA, Nowakowski TJ, Shuga J, Wang X, Leyrat AA, Lui JH, Li N, et al. (2014) Low-coverage single-cell mRNA sequencing reveals cellular heterogeneity and activated signaling pathways in developing cerebral cortex. Nature Biotechnology 32(10):1053–1058.Google Scholar
• Qi L, Sun J (1993) A nonsmooth version of Newton’s method. Math. Programming 58(1–3):353–367.Google Scholar
• Schlitzer A, Sivakamasundari V, Chen J, Sumatoh HRB, Schreuder J, Lum J, Malleret B, et al. (2015) Identification of cDC1-and cDC2-committed DC progenitors reveals early lineage priming at the common DC progenitor stage in the bone marrow. Nature Immunology 16(7):718–728.Google Scholar
• Shi J, Malik J (2000) Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Machine Intelligence 22(8):888–905.Google Scholar
• Strehl A, Ghosh J (2003) Cluster ensembles—A knowledge reuse framework for combining multiple partitions. J. Machine Learn. Res. 3:583–617.Google Scholar
• Sun J, Qu Q, Wright J (2017) Complete dictionary recovery over the sphere I: Overview and the geometric picture. IEEE Trans. Inform. Theory 63(2):853–884.Google Scholar
• Sun J, Qu Q, Wright J (2018) A geometrical analysis of phase retrieval. Foundations Comput. Math. 18(5):1131–1198.Google Scholar
• Tasic B, Menon V, Nguyen TN, Kim TK, Jarsky T, Yao Z, Levi B, et al. (2016) Adult mouse cortical cell taxonomy revealed by single cell transcriptomics. Nature Neuroscience 19:335–346.Google Scholar
• Ting DT, Wittner BS, Ligorio M, Jordan NV, Shah AM, Miyamoto DT, Aceto N, et al. (2014) Single-cell RNA sequencing identifies extracellular matrix gene expression by pancreatic circulating tumor cells. Cell Rep. 8(6):1905–1918.Google Scholar
• Treutlein B, Brownfield DG, Wu AR, Neff NF, Mantalas GL, Espinoza FH, Desai TJ, Krasnow MA, Quake SR (2014) Reconstructing lineage hierarchies of the distal lung epithelium using single-cell RNA-seq. Nature 509(7500):371–375.Google Scholar
• van der Maaten L, Hinton G (2008) Visualizing data using t-SNE. J. Machine Learn. Res. 9:2579–2605.Google Scholar
• Wang B, Ma S, Xue L (2020) Riemannian stochastic proximal gradient methods for nonsmooth optimization over the Stiefel manifold. Preprint, submitted May3, https://arxiv.org/abs/2005.01209.Google Scholar
• Wang B, Ramazzotti D, De Sano L, Zhu J, Pierson E, Batzoglou S (2017) SIMLR: A tool for large-scale single-cell analysis by multi-kernel learning. Proteomics 18(2):1700232.Google Scholar
• Wang C, Sun D, Toh KC (2010) Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm. SIAM J. Optim. 20(6):2994–3013.Google Scholar
• Xiao X, Li Y, Wen Z, Zhang L (2018) A regularized semi-smooth Newton method with projection steps for composite convex programs. J. Sci. Comput. 76:364–389.Google Scholar
• Yang J, Sun D, Toh KC (2013) A proximal point algorithm for log-determinant optimization with group Lasso regularization. SIAM J. Optim. 23(2):857–893.Google Scholar
• Yang WH, Zhang LH, Song R (2014) Optimality conditions for the nonlinear programming problems on Riemannian manifolds. Pacific J. Optim. 10(2):415–434.Google Scholar
• Zhao XY, Sun D, Toh KC (2010) A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4):1737–1765.Google Scholar