# Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment

arXiv: https://arxiv.org/abs/2110.11420 · HTML: https://mlsanity.com/paper/2110.11420/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 27 references that are in the map.
- First posted on arXiv 21 Oct 2021.

## Builds on (most cited first, 9 of 9)

- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [On the Computational Intractability of Exact and Approximate Dictionary Learning](https://mlsanity.com/paper/1405.6664/) (2014)
- [Random Walk Graph Laplacian based Smoothness Prior for Soft Decoding of JPEG Images](https://mlsanity.com/paper/1607.01895/) (2016)
- [Diversity-aware Multi-Video Summarization](https://mlsanity.com/paper/1706.03123/) (2017)
- [Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment](https://mlsanity.com/paper/1907.06179/) (2019)
- [Fast & Robust Image Interpolation using Gradient Graph Laplacian Regularizer](https://mlsanity.com/paper/2101.09951/) (2021)
- [Diversity Promoting Online Sampling for Streaming Video Summarization](https://mlsanity.com/paper/1610.09582/) (2016)

## Built on by (most cited first, 1 of 1)

- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)

## Abstract (arXiv)

We study the problem of efficiently summarizing a short video into several keyframes, leveraging recent progress in fast graph sampling. Specifically, we first construct a similarity path graph (SPG) G, represented by graph Laplacian matrix L, where the similarities between adjacent frames are encoded as positive edge weights. We show that maximizing the smallest eigenvalue λmin(B) of a coefficient matrix B = diag(a) + μ L, where a is the binary keyframe selection vector, is equivalent to minimizing a worst-case signal reconstruction error. We prove that, after partitioning G into Q sub-graphs GqQq=1, the smallest Gershgorin circle theorem (GCT) lower bound of Q corresponding coefficient matrices -- minq λ^-min(Bq) -- is a lower bound for λmin(B). This inspires a fast graph sampling algorithm to iteratively partition G into Q sub-graphs using Q samples (keyframes), while maximizing λ^-min(Bq) for each sub-graph Gq. Experimental results show that our algorithm achieves comparable video summarization performance as state-of-the-art methods, at a substantially reduced complexity.