Article
Mathematics, Applied
Richard Kueng, Joel A. Tropp
Summary: This paper investigates the decomposition of a low-rank positive-semidefinite matrix into symmetric factors with binary entries and provides answers to fundamental questions regarding the existence and uniqueness of these decompositions. The research also introduces tractable factorization algorithms that work under a mild deterministic condition.
SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE
(2021)
Article
Computer Science, Software Engineering
Milan Korda, Monique Laurent, Victor Magron, Andries Steenkamp
Summary: We introduce a new type of sparsity, called ideal-sparsity, for the generalized moment problem (GMP). By optimizing over a measure supported on the variety of an ideal generated by quadratic bilinear monomials, we obtain an equivalent sparse reformulation of GMP. The resulting hierarchies of moment-based relaxations for ideal-sparse reformulation provide tighter bounds and are computationally faster than the dense analogs.
MATHEMATICAL PROGRAMMING
(2023)
Article
Engineering, Electrical & Electronic
Dana Lahat, Yanbin Lang, Vincent Y. F. Tan, Cedric Fevotte
Summary: Positive semidefinite matrix factorization (PSDMF) expresses nonnegative matrices as the inner product of two positive semidefinite matrices. By leveraging phase retrieval and affine rank minimization algorithms, new PSDMF algorithms can be designed for a more efficient optimization process. High variability in PSDMF problems necessitates trying a variety of methods, with some cases showing our proposed methods as the only ones able to find solutions.
IEEE TRANSACTIONS ON SIGNAL PROCESSING
(2021)
Article
Operations Research & Management Science
April Sagan, John E. Mitchell
Summary: This study introduces an algorithm based on nuclear norm and low rank factorization for solving the rank minimization problem, which has less estimation bias and can reduce the effect of noise on measurements compared to convex relaxations. By iteratively reweighted nuclear norm schemes, it efficiently solves the rank minimization problem for large matrices.
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
(2021)
Article
Mathematics, Applied
Stefania Bellavia, Jacek Gondzio, Margherita Porcelli
Summary: This paper introduces a new relaxed variant of interior point method for low-rank semidefinite programming problems, imposing a special nearly low-rank form of all primal iterates and approximating the first order optimality conditions by solving an auxiliary least-squares problem. The method allows for the computation of both primal and dual approximated Newton directions, and its convergence has been established, with promising preliminary computational results for solving SDP-reformulation of matrix-completion problems.
JOURNAL OF SCIENTIFIC COMPUTING
(2021)
Article
Computer Science, Artificial Intelligence
Zhongbao Zhang, Li Sun, Sen Su, Jielun Qu, Gen Li
Summary: Recently, there has been significant attention on reconciling social networks and identifying accounts belonging to the same individual across different platforms. Existing studies have limitations in terms of multiplicity, comprehensiveness, and robustness. To address these limitations, the paper proposes two frameworks, MASTER and MASTER+, that robustly and comprehensively reconcile multiple social networks, outperforming existing approaches. MASTER+ further enhances efficiency by grouping accounts into clusters and performing reconciliation in parallel.
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
(2021)
Article
Mathematics, Applied
Ran Gu, Qiang Du, Ya-xiang Yuan
Summary: Quadratically constrained quadratic programming (QCQP) is prevalent in engineering applications, and we have proposed a penalty formulation based on semidefinite relaxation to tackle this NP-hard problem. Our algorithm has been shown to be very effective in finding high-quality solutions through numerical testing on well-studied QCQP problems.
IMA JOURNAL OF NUMERICAL ANALYSIS
(2021)
Article
Mathematics
Naomi Shaked-Monderer
Summary: A square matrix A is completely positive if it can be expressed as A = BBT, where B is a nonnegative matrix that may not necessarily be square. While a completely positive matrix can have multiple CP factorizations, there are cases where a unique CP factorization exists. A simple necessary and sufficient condition has been proven for a completely positive matrix with a triangle-free graph to have a unique CP factorization. This also implies uniqueness of the CP factorization for certain matrices on the boundary of the cone of completely positive matrices.
LINEAR & MULTILINEAR ALGEBRA
(2022)
Article
Engineering, Electrical & Electronic
Shuang Xu, Jiangshe Zhang, Chunxia Zhang
Summary: This paper proposes a new method for hyperspectral image denoising, called Hyper-Laplacian spectral-spatial total variation (HTV), and designs two low-rank models. Experimental results demonstrate the superiority of the HTV method over traditional TV regularization methods and other commonly used hyperspectral image denoising algorithms.
Article
Operations Research & Management Science
Hamza Fawzi
Summary: This paper establishes lower bounds on the complexity of approximating semidefinite programs with linear programs, showing that any polytope approximating the positive semidefinite cone must have at least superpolynomial extension complexity. Ultimately, there is no generic way to efficiently approximate semidefinite programs with compact linear programs.
MATHEMATICS OF OPERATIONS RESEARCH
(2021)
Article
Computer Science, Information Systems
Derek Desantis, Erik Skau, Duc P. Truong, Boian Alexandrov
Summary: This work examines the factorizations of binary matrices using standard arithmetic and logical operations, and discusses the uniqueness conditions of the factorization. The introduced method BMFk accurately determines the number of Boolean latent features and reconstructs the factors.
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
(2022)
Article
Operations Research & Management Science
Diego Cifuentes
Summary: The Burer-Monteiro method can solve equality-constrained semidefinite programs with a generic cost matrix, as shown by Boumal et al. This study extends their result to arbitrary semidefinite programs, including inequalities or multiple constraints, deriving similar guarantees for fixed cost matrix and generic constraints. Applications to matrix sensing and integer quadratic minimization are also illustrated.
OPTIMIZATION LETTERS
(2021)
Article
Computer Science, Software Engineering
Yuya Yamakawa, Tetsuya Ikegami, Ellen H. H. Fukuda, Nobuo Yamashita
Summary: In this paper, a new nonlinear optimization model is proposed to solve semidefinite optimization problems (SDPs), and some properties related to local optimal solutions are provided. The proposed model is based on another nonlinear optimization model, but it has several nice properties not seen in the existing one. The decision variable of the proposed model is a triangular low-rank matrix, and the existence of a strict local optimum is guaranteed.
OPTIMIZATION METHODS & SOFTWARE
(2023)
Article
Mathematics, Applied
Hong Zhu, Michael K. Ng, Guang-Jing Song
Summary: A new approximate method for solving nonnegative low-rank matrix approximation problem is developed in this study. It involves alternately projecting onto fixed-rank matrix manifold and nonnegative matrix manifold to ensure convergence, with numerical results demonstrating its performance.
JOURNAL OF SCIENTIFIC COMPUTING
(2021)
Article
Mathematics, Applied
Gilbert Strang, Cleve Moler
Summary: This paper introduces a new matrix factorization method, which decomposes matrix A into column matrix C and row matrix R, and reimagines the start of a linear algebra course by observing the independent columns, rank, and column space of A.
Article
Operations Research & Management Science
Xavier Fernandes, Joana Rebelo, Joao Gouveia, Rodrigo Maia, Nuno Bustorff Silva
4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH
(2017)
Article
Mathematics
Joao Gouveia, Kanstanstin Pashkovich, Richard Z. Robinson, Rekha R. Thomas
JOURNAL OF COMBINATORIAL THEORY SERIES A
(2017)
Article
Computer Science, Theory & Methods
Hamza Fawzi, James Saunderson, Pablo A. Parrilo
FOUNDATIONS OF COMPUTATIONAL MATHEMATICS
(2019)
Article
Mathematics, Applied
Joao Gouveia, Antonio Macchia, Rekha R. Thomas, Amy Wiebe
JOURNAL OF PURE AND APPLIED ALGEBRA
(2020)
Article
Operations Research & Management Science
Joao Gouveia, Ting Kei Pong, Mina Saee
JOURNAL OF GLOBAL OPTIMIZATION
(2020)
Article
Computer Science, Theory & Methods
Tristram Bogart, Joao Gouveia, Juan Camilo Torres
Summary: In this paper, the authors merge geometric and algebraic approaches to projective uniqueness and show that McMullen's operations not only preserve projective uniqueness but also graphicality. As an application, they demonstrate that large families of order polytopes are graphic and thus projectively unique.
DISCRETE & COMPUTATIONAL GEOMETRY
(2022)
Article
Mathematics, Applied
Joao Gouveia, Alexander Kovacec, Mina Saee
Summary: Introduced in 2005 by Boman et al., factor width for a real symmetric positive semidefinite matrix determines the smallest positive integer k for which the matrix can be expressed as A = VVT with each column of V containing at most k non-zeros. This concept has practical implications in the context of polynomial optimization and the connections between polynomials and sums of squares.
JOURNAL OF PURE AND APPLIED ALGEBRA
(2022)
Article
Computer Science, Theory & Methods
Joao Gouveia, Antonio Macchia, Amy Wiebe
Summary: This paper examines four different models for the realization space of a polytope and explores their relationships and how to combine the strengths of different models. By combining the compact nature of the Grassmannian model with the slack variety, a reduced slack model is obtained, which further expands the research on the realization of polytopes.
DISCRETE & COMPUTATIONAL GEOMETRY
(2023)
Article
Mathematics, Applied
Hamza Fawzi, Joao Gouveia, Pablo A. Parrilo, James Saunderson, Rekha R. Thomas
Summary: This paper presents a survey of the theory and applications of lifts of convex sets, focusing on polyhedral lifts and spectrahedral lifts. It explains the connection between the existence of lifts and structured factorizations of the associated slack operator, and provides a unified approach for constructing spectrahedral lifts using sums of squares. The paper also discusses two types of obstructions to the existence of lifts: facial structure obstruction and algebraic properties obstruction. It aims to illustrate the richness of the area by providing various examples of lifts from different areas of mathematics and its applications.
Article
Mathematics, Applied
Tristram Bogart, Joao Gouveia, Juan Camilo Torres
Summary: The research focuses on the characteristics of complex psd-minimal polytopes. An efficiently computable obstruction to complex psd-minimality is proved to exist, and this tool is used to complete the classification of complex psd-minimal polygons. Several new examples of complex psd-minimal polytopes are presented in three-dimensional space, and our obstruction is applied to rule out many other cases.
JOURNAL OF ALGEBRA AND ITS APPLICATIONS
(2022)
Article
Computer Science, Theory & Methods
Joao Gouveia, Antonio Macchia, Amy Wiebe
Summary: This paper presents a simple technique to derive certificates of non-realizability for combinatorial polytopes. The approach uses a variant of classical algebraic certificates called final polynomials. The proposed method is more straightforward, using linear programming to exhaustively search for positive polynomials in a specific linear subspace to demonstrate non-realizability.
JOURNAL OF SYMBOLIC COMPUTATION
(2023)
Article
Mathematics, Applied
Joao Gouveia, Bruno F. Lourenco
Summary: In this paper, we analyze self-dual polyhedral cones and prove properties related to their slack matrices. We demonstrate that self-duality is equivalent to the existence of a positive semi-definite slack matrix. Furthermore, we show that if the underlying cone is irreducible, the corresponding PSD slacks are not only doubly nonnegative matrices but also extreme rays of the cone of DNN matrices. Additionally, we find that unless the cone is simplicial, PSD slacks not only fail to be completely positive matrices but they also lie outside the cone of completely positive semidefinite matrices. Finally, we discuss how semidefinite programming can be used to determine the existence of self-dual cones with specific combinatorial properties.
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS
(2023)
Article
Mathematics, Applied
Antonio Pedro Goucha, Joao Gouveia
Summary: In this paper, the concept of phaseless rank of a complex matrix is discussed and connected to determinantal varieties, semidefinite representations of convex sets, and the complexity of polytopes. New results are derived and an upper bound on the complex semidefinite extension complexity of polytopes is obtained. The study also highlights the connections between phaseless rank and the problem of finding large sets of complex equiangular lines or mutually unbiased bases.
SIAM JOURNAL ON APPLIED ALGEBRA AND GEOMETRY
(2021)
Article
Mathematics, Applied
Joao Gouveia, Antonio Macchia, Rekha R. Thomas, Amy Wiebe
SIAM JOURNAL ON DISCRETE MATHEMATICS
(2019)
