اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدEfficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices
147
0
0.0
(
0
)
نشر من قبل
Kirankumar Shiragur
تاريخ النشر
2018
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper we show how to recover a spectral approximations to broad classes of structured matrices using only a polylogarithmic number of adaptive linear measurements to either the matrix or its inverse. Leveraging this result we obtain faster algorithms for variety of linear algebraic problems. Key results include: $bullet$ A nearly linear time algorithm for solving the inverse of symmetric $M$-matrices, a strict superset of Laplacians and SDD matrices. $bullet$ An $tilde{O}(n^2)$ time algorithm for solving $n times n$ linear systems that are constant spectral approximations of Laplacians or more generally, SDD matrices. $bullet$ An $tilde{O}(n^2)$ algorithm to recover a spectral approximation of a $n$-vertex graph using only $tilde{O}(1)$ matrix-vector multiplies with its Laplacian matrix. The previous best results for each problem either used a trivial number of queries to exactly recover the matrix or a trivial $O(n^omega)$ running time, where $omega$ is the matrix multiplication constant. We achieve these results by generalizing recent semidefinite programming based linear sized sparsifier results of Lee and Sun (2017) and providing iterative methods inspired by the semistreaming sparsification results of Kapralov, Lee, Musco, Musco and Sidford (2014) and input sparsity time linear system solving results of Li, Miller, and Peng (2013). We hope that by initiating study of these natural problems, expanding the robustness and scope of recent nearly linear time linear system solving research, and providing general matrix recovery machinery this work may serve as a stepping stone for faster algorithms.
قيم البحث
اقرأ أيضاً
In this paper we provide an $tilde{O}(nd+d^{3})$ time randomized algorithm for solving linear programs with $d$ variables and $n$ constraints with high probability. To obtain this result we provide a robust, primal-dual $tilde{O}(sqrt{d})$-iteration
interior point method inspired by the methods of Lee and Sidford (2014, 2019) and show how to efficiently implement this method using new data-structures based on heavy-hitters, the Johnson-Lindenstrauss lemma, and inverse maintenance. Interestingly, we obtain this running time without using fast matrix multiplication and consequently, barring a major advance in linear system solving, our running time is near optimal for solving dense linear programs among algorithms that do not use fast matrix multiplication.
In this paper we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors, i.e. entrywise non-negative eigenvectors of non-negative matrices, and solvi
ng linear systems in asymmetric M-matrices, a generalization of Laplacian systems. The running times of our algorithms depend nearly linearly on the input size and polylogarithmically on the desired accuracy and problem condition number. Leveraging these results we also provide improved running times for a broader range of problems including computing random walk-based graph kernels, computing Katz centrality, and more. The running times of our algorithms improve upon previously known results which either depended polynomially on the condition number of the problem, required quadratic time, or only applied to special cases. We obtain these results by providing new iterative methods for reducing these problems to solving linear systems in Row-Column Diagonally Dominant (RCDD) matrices. Our methods are related to the classic shift-and-invert preconditioning technique for eigenvector computation and constitute the first alternative to the result in Cohen et al. (2016) for reducing stationary distribution computation and solving directed Laplacian systems to solving RCDD systems.
In this paper we provide new randomized algorithms with improved runtimes for solving linear programs with two-sided constraints. In the special case of the minimum cost flow problem on $n$-vertex $m$-edge graphs with integer polynomially-bounded cos
ts and capacities we obtain a randomized method which solves the problem in $tilde{O}(m+n^{1.5})$ time. This improves upon the previous best runtime of $tilde{O}(msqrt{n})$ (Lee-Sidford 2014) and, in the special case of unit-capacity maximum flow, improves upon the previous best runtimes of $m^{4/3+o(1)}$ (Liu-Sidford 2020, Kathuria 2020) and $tilde{O}(msqrt{n})$ (Lee-Sidford 2014) for sufficiently dense graphs. For $ell_1$-regression in a matrix with $n$-columns and $m$-rows we obtain a randomized method which computes an $epsilon$-approximate solution in $tilde{O}(mn+n^{2.5})$ time. This yields a randomized method which computes an $epsilon$-optimal policy of a discounted Markov Decision Process with $S$ states and $A$ actions per state in time $tilde{O}(S^2A+S^{2.5})$. These methods improve upon the previous best runtimes of methods which depend polylogarithmically on problem parameters, which were $tilde{O}(mn^{1.5})$ (Lee-Sidford 2015) and $tilde{O}(S^{2.5}A)$ (Lee-Sidford 2014, Sidford-Wang-Wu-Ye 2018). To obtain this result we introduce two new algorithmic tools of independent interest. First, we design a new general interior point method for solving linear programs with two sided constraints which combines techniques from (Lee-Song-Zhang 2019, Brand et al. 2020) to obtain a robust stochastic method with iteration count nearly the square root of the smaller dimension. Second, to implement this method we provide dynamic data structures for efficiently maintaining approximations to variants of Lewis-weights, a fundamental importance measure for matrices which generalize leverage scores and effective resistances.
We present an $tilde O(m+n^{1.5})$-time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, and optimal transport) on $m$-edge, $n$-node graphs. For maximum cardina
lity bipartite matching on moderately dense graphs, i.e. $m = Omega(n^{1.5})$, our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic $O(msqrt{n})$-time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and $tilde O(n^omega)$-time algorithms [Ibarra-Moran 1981] (where currently $omegaapprox 2.373$). On sparser graphs, i.e. when $m = n^{9/8 + delta}$ for any constant $delta>0$, our result improves upon the recent advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an $tilde O(m^{4/3+o(1)})$ runtime. We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v.d.Brand-Lee-Sidford-Song 2020], providing a general primal-dual IPM framework and new sampling-based techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublinear-time algorithm for detecting and sampling high-energy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates of both [v.d.Brand et al.] and our new IPMs. Combining this general machinery yields a simpler $tilde O(n sqrt{m})$ time algorithm for matching based on the logarithmic barrier function, and our state-of-the-art $tilde O(m+n^{1.5})$ time algorithm for matching based on the [Lee-Sidford 2014] barrier (as regularized in [v.d.Brand et al.]).
A skew-symmetric graph $(D=(V,A),sigma)$ is a directed graph $D$ with an involution $sigma$ on the set of vertices and arcs. In this paper, we introduce a separation problem, $d$-Skew-Symmetric Multicut, where we are given a skew-symmetric graph $D$,
a family of $cal T$ of $d$-sized subsets of vertices and an integer $k$. The objective is to decide if there is a set $Xsubseteq A$ of $k$ arcs such that every set $J$ in the family has a vertex $v$ such that $v$ and $sigma(v)$ are in different connected components of $D=(V,Asetminus (Xcup sigma(X))$. In this paper, we give an algorithm for this problem which runs in time $O((4d)^{k}(m+n+ell))$, where $m$ is the number of arcs in the graph, $n$ the number of vertices and $ell$ the length of the family given in the input. Using our algorithm, we show that Almost 2-SAT has an algorithm with running time $O(4^kk^4ell)$ and we obtain algorithms for {sc Odd Cycle Transversal} and {sc Edge Bipartization} which run in time $O(4^kk^4(m+n))$ and $O(4^kk^5(m+n))$ respectively. This resolves an open problem posed by Reed, Smith and Vetta [Operations Research Letters, 2003] and improves upon the earlier almost linear time algorithm of Kawarabayashi and Reed [SODA, 2010]. We also show that Deletion q-Horn Backdoor Set Detection is a special case of 3-Skew-Symmetric Multicut, giving us an algorithm for Deletion q-Horn Backdoor Set Detection which runs in time $O(12^kk^5ell)$. This gives the first fixed-parameter tractable algorithm for this problem answering a question posed in a paper by a superset of the authors [STACS, 2013]. Using this result, we get an algorithm for Satisfiability which runs in time $O(12^kk^5ell)$ where $k$ is the size of the smallest q-Horn deletion backdoor set, with $ell$ being the length of the input formula.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
