Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment

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.