More Like this

1. Sparks of symmetric matrices and their graphs

   https://doi.org/10.13001/ela.2023.8025  

   Deaett, Louis; Fallat, Shaun; Furst, Veronika; Hutchens, John; Mitchell, Lon; Zhang, Yaqi (November 2023, The Electronic Journal of Linear Algebra)

   The spark of a matrix is the smallest number of nonzero coordinates of any nonzero null vector. For real symmetric matrices, the sparsity of null vectors is shown to be associated with the structure of the graph obtained from the off-diagonal pattern of zero and nonzero entries. The smallest possible spark of a matrix corresponding to a graph is defined as the spark of the graph. Connections are established between graph spark and well-known concepts including minimum rank, forts, orthogonal representations, Parter and Fiedler vertices, and vertex connectivity. 

   more » « less
2. Approximation Algorithms for Orthogonal Non-negative Matrix Factorization

   Charikar, Moses; Hu, Lunjia (January 2021, Proeedings of the International Workshop on Artificial Intelligence and Statistics)

   null (Ed.)

   In the non-negative matrix factorization (NMF) problem, the input is an m×n matrix M with non-negative entries and the goal is to factorize it as M ≈ AW. The m × k matrix A and the k × n matrix W are both constrained to have non-negative entries. This is in contrast to singular value decomposition, where the matrices A and W can have negative entries but must satisfy the orthogonality constraint: the columns of A are orthogonal and the rows of W are also orthogonal. The orthogonal non-negative matrix factorization (ONMF) problem imposes both the non-negativity and the orthogonality constraints, and previous work showed that it leads to better performances than NMF on many clustering tasks. We give the first constant-factor approximation algorithm for ONMF when one or both of A and W are subject to the orthogonality constraint. We also show an interesting connection to the correlation clustering problem on bipartite graphs. Our experiments on synthetic and real-world data show that our algorithm achieves similar or smaller errors compared to previous ONMF algorithms while ensuring perfect orthogonality (many previous algorithms do not satisfy the hard orthogonality constraint). 

   more » « less
3. The non-symmetric strong multiplicity property for sign patterns

   https://doi.org/10.13001/ela.2025.8827  

   Curtis, Bryan; Garnett, Colin; Shader, Bryan L; Vander_Meulen, Kevin N (January 2025, The Electronic Journal of Linear Algebra)

   We develop a non-symmetric strong multiplicity property for matrices that may or may not be symmetric. We say a sign pattern allows the non-symmetric strong multiplicity property if there is a matrix with the non-symmetric strong multiplicity property that has the given sign pattern. We show that this property of a matrix pattern preserves multiplicities of eigenvalues for superpatterns of the pattern. We also provide a bifurcation lemma, showing that a matrix pattern with the property also allows refinements of the multiplicity list of eigenvalues. We conclude by demonstrating how this property can help with the inverse eigenvalue problem of determining the number of distinct eigenvalues allowed by a sign pattern. 

   more » « less
4. Minimum number of non-zero-entries in a stable matrix exhibiting Turing instability

   https://doi.org/10.3934/dcdss.2021128  

   Hambric, Christopher Logan; Li, Chi-Kwong; Pelejo, Diane Christine; Shi, Junping (January 2022, Discrete and Continuous Dynamical Systems - S)

   It is shown that for any positive integer \begin{document}$$ n \ge 3 $$\end{document}, there is a stable irreducible \begin{document}$$ n\times n $$\end{document} matrix \begin{document}$ A $$\end{document} with \begin{document}$$ 2n+1-\lfloor\frac{n}{3}\rfloor $$\end{document} nonzero entries exhibiting Turing instability. Moreover, when \begin{document}$$ n = 3 $$\end{document}, the result is best possible, i.e., every \begin{document}$$ 3\times 3 $$\end{document} stable matrix with five or fewer nonzero entries will not exhibit Turing instability. Furthermore, we determine all possible \begin{document}$$ 3\times 3 $$\end{document} irreducible sign pattern matrices with 6 nonzero entries which can be realized by a matrix \begin{document}$$ A $$\end{document}$ that exhibits Turing instability. 

   more » « less
5. Distributed-Memory Randomized Algorithms for Sparse Tensor CP Decomposition

   https://doi.org/10.1145/3626183.3659980  

   Bharadwaj, Vivek; Malik, Osman Asif; Murray, Riley; Buluc, Aydin; Demmel, James (June 2024, Annual ACM Symposium on Parallelism in Algorithms and Architectures)

   Candecomp / PARAFAC (CP) decomposition, a generalization of the matrix singular value decomposition to higher-dimensional tensors, is a popular tool for analyzing multidimensional sparse data. On tensors with billions of nonzero entries, computing a CP decomposition is a computationally intensive task. We propose the first distributed-memory implementations of two randomized CP decomposition algorithms,CP-ARLS-LEV and STS-CP, that offer nearly an order-of-magnitude speedup at high decomposition ranks over well-tuned non-randomized decomposition packages. Both algorithms rely on leverage score sampling and enjoy strong theoretical guarantees, each with varying time and accuracy tradeoffs. We tailor the communication schedule for our random sampling algorithms, eliminating expensive reduction collectives and forcing communication costs to scale with the random sample count. Finally, we optimize the local storage format for our methods, switching between analogues of compressed sparse column and compressed sparse row formats. Experiments show that our methods are fast and scalable,producing 11x speedup over SPLATT by decomposing the billion-scale Reddit tensor on 512 CPU cores in under two minutes. 

   more » « less