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"”.

  1. 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 …

    bu Repository record for A regularization perspective on spectral sparsification (opens in a new tab)

  2. 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 …

    gatech Repository record for A Fast Parallel Density-aware Algorithm for Graph Spectral Sparsification (opens in a new tab)

  3. 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 …

    waterloo Repository record for A Spectral Approach to Network Design and Experimental Design (opens in a new tab)

  4. Γεωμετρική συναρτησιακή ανάλυση και εφαρμογές στη συνδυαστική

    … 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 …

    greece Repository record for Γεωμετρική συναρτησιακή ανάλυση και εφαρμογές στη συνδυαστική (opens in a new tab)

  5. 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 …

    mtu Repository record for HIGH PERFORMANCE SPECTRAL METHODS FOR GRAPH-BASED MACHINE LEARNING (opens in a new tab)

  6. 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 …

    waterloo Repository record for A Primal-Dual Framework for Approximation Algorithms using Semidefinite Programming (opens in a new tab)

  7. 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 …

    bu Repository record for Methods, algorithms and impossibility results for machine learning on graphs (opens in a new tab)

  8. 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 …

    texas Repository record for Using and saving randomness (opens in a new tab)

  9. 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 …

    usf Repository record for Scalable Unsupervised Learning with Game Theory (opens in a new tab)

  10. 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 …

    mtu Repository record for HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS (opens in a new tab)

  11. 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 …

    gatech Repository record for Bridging Discrete and Continuous Methods for Faster Optimization and Machine Learning (opens in a new tab)