School of Science Department of Mathematics 46 Low-Rank and Sparsity Reconstruction in Data Science Supervisor: CAI Jianfeng / MATH Co-Supervisor: YE Guibo / MATH Student: WANG Kailin / DSCT Course: UROP 1100, Spring Matrix completion addresses the challenge of recovering missing entries in partially observed datasets, a problem ubiquitous in data science applications. Under structural assumptions such as low-rankness of the matrix and uniform sampling, this task is often formulated as a rank minimization problem subject to known information. However, the non-convex and NP-hard nature of rank minimization necessitates relaxation to computationally tractable alternatives. This report converts rank minimization problems into nuclear norm minimization problems, highlighting its theoretical guarantees, the high-probability recovery of unique solutions under necessary assumptions, and its vital role in bridging computational feasibility with robust matrix recovery. Chromatic Polynomials of Graphs and Signed Graphs Supervisor: CHEN Beifang / MATH Student: QING Mengze / MATH-PMA Course: UROP 1000, Summer This paper introduces out-edge graphs, defined as ordered tuples ( , , , ) that extend standard graphs with out-edges (edges incident to exactly one vertex). We establish an Out-edge Decomposition Theorem demonstrating that any graph cut [ , ] decomposes into two out-edge graphs Å and B̊. This decomposition yields a fundamental result: the chain space of an out-edge graph is isomorphic to that of its completion graph. Key contributions include: (1) preservation of flows and tensions under decomposition, where flows/tensions on induce corresponding structures on Å and B̊ ; (2) incidence matrix correspondence showing that decomposed graph matrices are submatrices of ’s incidence matrix; and (3) a generalized Kirchhoff’s theorem proving that the number of spanning trees in an out-edge graph equals the determinant of its Laplacian matrix.
RkJQdWJsaXNoZXIy NDk5Njg=