17 citations · 19 across the 7 of their papers we have counts for
9 papers
On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
Tsz Chiu Kwok, Zhewei Wei, Mingji Yang
We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system in sublinear time, with the goal of estimating for a given vector $t\in…
Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung
The classical Cheeger's inequality relates the edge conductance of a graph and the second smallest eigenvalue of the Laplacian matrix. Recently, Olesker-Taylor and Zanett…
Spectral analysis of matrix scaling and operator scaling
Tsz Chiu Kwok, Lap Chi Lau, Akshay Ramachandran
We present a spectral analysis for matrix scaling and operator scaling. We prove that if the input matrix or operator has a spectral gap, then a natural gradient flow has linear co…
The Paulsen Problem, Continuous Operator Scaling, and Smoothed Analysis
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee +1
The Paulsen problem is a basic open problem in operator theory: Given vectors that are -nearly satisfying the Parseval's condition and the equ…
Random Walks and Evolving Sets: Faster Convergences and Limitations
Siu On Chan, Tsz Chiu Kwok, Lap Chi Lau
Analyzing the mixing time of random walks is a well-studied problem with applications in random sampling and more recently in graph partitioning. In this work, we present new analy…
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee
We prove two generalizations of the Cheeger's inequality. The first generalization relates the second eigenvalue to the edge expansion and the vertex expansion of the graph G, $λ_2…
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee +2
Let ϕ(G) be the minimum conductance of an undirected graph G, and let 0=λ_1 <= λ_2 <=... <= λ_n <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for a…
Finding Small Sparse Cuts Locally by Random Walk
Tsz Chiu Kwok, Lap Chi Lau
We study the problem of finding a small sparse cut in an undirected graph. Given an undirected graph G=(V,E) and a parameter k <= |E|, the small sparsest cut problem is to find a s…
Fast Matrix Rank Algorithms and Applications
Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau
We consider the problem of computing the rank of an m x n matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in Õ(|A…