2026-08-04T17:24:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9421 2024-03-06T10:44:21Z ddc:004 open_access

Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices Levi, Amit Yoshida, Yuichi Qudratic function minimization Approximation Algorithms Matrix spectral decomposition Graph limits We design a sublinear-time approximation algorithm for quadratic function minimization problems with a better error bound than the previous algorithm by Hayashi and Yoshida (NIPS'16). Our approximation algorithm can be modified to handle the case where the minimization is done over a sphere. The analysis of our algorithms is obtained by combining results from graph limit theory, along with a novel spectral decomposition of matrices. Specifically, we prove that a matrix A can be decomposed into a structured part and a pseudorandom part, where the structured part is a block matrix with a polylogarithmic number of blocks, such that in each block all the entries are the same, and the pseudorandom part has a small spectral norm, achieving better error bound than the existing decomposition theorem of Frieze and Kannan (FOCS'96). As an additional application of the decomposition theorem, we give a sublinear-time approximation algorithm for computing the top singular values of a matrix. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amit Levi and Yuichi Yoshida 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.17 urn:nbn:de:0030-drops-94210 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.17 eng https://creativecommons.org/licenses/by/3.0/legalcode