17 citations · 17 across the 3 of their papers we have counts for
5 papers
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…