Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 11 of 11 for “"Spectral Sparsification"”.
-
A regularization perspective on spectral sparsification
… we study how to obtain faster algorithms for spectral graph sparsifi-cation by applying continuous optimization techniques. Spectral sparsification is thetask of reducing the number of edges in a graph while maintaining a spectral ap-proximation to the original graph. Our key conceptual …
-
A Fast Parallel Density-aware Algorithm for Graph Spectral Sparsification
Graph Spectral Sparsification (GSS) identifies an ultra-sparse subgraph, or sparsifier, whose Laplacian matrix closely approximates the spectral properties of the original graph, enabling substantial reductions in computational complexity for computationally intensive problems in scientific …
-
A Spectral Approach to Network Design and Experimental Design
Over the last decade, the spectral sparsification technique has become a powerful tool in designing fast graph algorithms for various problems with numerous applications. In this thesis, we extend this spectral approach, and show that it is also very powerful in designing approximation algorithms …
-
Γεωμετρική συναρτησιακή ανάλυση και εφαρμογές στη συνδυαστική
… result. One of the basic tools used is the spectral sparsification and a new Brascamp Lieb inequality.In the second part, new local inequalities are demonstrated for the volume of the convex body with main subspaces. These is a Loomis Whitney type. Based on the above, we find bounds for the …
-
HIGH PERFORMANCE SPECTRAL METHODS FOR GRAPH-BASED MACHINE LEARNING
… application of a two-phase spectrum-preserving spectral sparsification method that enables to construct very sparse sparsifiers with guaranteed preservation of original graph spectra for spectral clustering. Experiments show that the computational challenge due to the eigen-decomposition …
-
A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming
… approximation algorithms, convex optimization, spectral sparsification, and measure concentration. A Banach-space version of our framework provides a novel approach for the design of rounding algorithms, and tightens the relationship between approximation algorithms for CSPs and the work of …
-
Methods, algorithms and impossibility results for machine learning on graphs
… detection and introduce a novel triangle-aware spectral sparsification algorithm that enhances the efficiency of this task. Secondly, we analyze a Twitter dataset and create a supervised learning framework that leverages the multiple layers of interaction among Twitter users, resulting in a more …
-
Using and saving randomness
… we improve the sample complexity to O(d) via spectral sparsification (optimal up to a constant factor), which provides the best known result for a range of linear families such as low degree multivariate polynomials. Next, we generalize this result to an active learning setting, where we get a …
-
Scalable Unsupervised Learning with Game Theory
… clustering scalable, we study the effect of the spectral sparsification method based on sampling by effective resistance on the clustering outputs. Through experimental and theoretical observations, we show that the clustering results obtained from sparsified graphs are very similar to the …
-
HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS
Recent research shows that by leveraging the key spectral properties of eigenvalues and eigenvectors of graph Laplacians, more efficient algorithms can be developed for tackling many graph-related computing tasks. In this dissertation, spectral methods are utilized for achieving faster algorithms …
-
Bridging Discrete and Continuous Methods for Faster Optimization and Machine Learning
With the machine learning and automation age we are in, it has become commonplace for algorithms to make decisions that impact our lives. Many such algorithms use optimization solvers as a subroutine, and there has been a revived interest in using robust approaches (like first-order optimization …