Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment
- URL: http://arxiv.org/abs/2110.11420v2
- Date: Mon, 25 Oct 2021 02:31:51 GMT
- Title: Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment
- Authors: Sadid Sahami, Gene Cheung, Chia-Wen Lin
- Abstract summary: We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling.
Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
- Score: 52.577757919003844
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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) $\mathcal{G}$, represented by
graph Laplacian matrix $\mathbf{L}$, where the similarities between adjacent
frames are encoded as positive edge weights. We show that maximizing the
smallest eigenvalue $\lambda_{\min}(\mathbf{B})$ of a coefficient matrix
$\mathbf{B} = \text{diag}(\mathbf{a}) + \mu \mathbf{L}$, where $\mathbf{a}$ is
the binary keyframe selection vector, is equivalent to minimizing a worst-case
signal reconstruction error. We prove that, after partitioning $\mathcal{G}$
into $Q$ sub-graphs $\{\mathcal{G}^q\}^Q_{q=1}$, the smallest Gershgorin circle
theorem (GCT) lower bound of $Q$ corresponding coefficient matrices -- $\min_q
\lambda^-_{\min}(\mathbf{B}^q)$ -- is a lower bound for
$\lambda_{\min}(\mathbf{B})$. This inspires a fast graph sampling algorithm to
iteratively partition $\mathcal{G}$ into $Q$ sub-graphs using $Q$ samples
(keyframes), while maximizing $\lambda^-_{\min}(\mathbf{B}^q)$ for each
sub-graph $\mathcal{G}^q$. Experimental results show that our algorithm
achieves comparable video summarization performance as state-of-the-art
methods, at a substantially reduced complexity.
Related papers
- Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive.
We summarize a transitory UGV into several discs in linear time via fast graph sampling based on Gershgorin disc alignment (GDA)
We show that our algorithm achieves comparable or better video summarization performance compared to state-of-the-art methods, at a substantially reduced complexity.
arXiv Detail & Related papers (2024-08-03T20:08:02Z) - Provably learning a multi-head attention layer [55.2904547651831]
Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models.
In this work, we initiate the study of provably learning a multi-head attention layer from random examples.
We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
arXiv Detail & Related papers (2024-02-06T15:39:09Z) - Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
This paper considers the task of linear regression with shuffled labels.
$mathbf Y in mathbb Rntimes m, mathbf Pi in mathbb Rntimes p, mathbf B in mathbb Rptimes m$, and $mathbf Win mathbb Rntimes m$, respectively.
arXiv Detail & Related papers (2023-10-02T16:44:47Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights.
We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs.
Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
arXiv Detail & Related papers (2022-08-18T09:19:01Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations.
The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
arXiv Detail & Related papers (2022-06-17T17:55:43Z) - Optimal Gradient Sliding and its Application to Distributed Optimization
Under Similarity [121.83085611327654]
We structured convex optimization problems with additive objective $r:=p + q$, where $r$ is $mu$-strong convex similarity.
We proposed a method to solve problems master to agents' communication and local calls.
The proposed method is much sharper than the $mathcalO(sqrtL_q/mu)$ method.
arXiv Detail & Related papers (2022-05-30T14:28:02Z) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
We leverage existing fast extreme eigenvector computation algorithms for speedy execution.
Our embedding is among the fastest in the literature, while producing the best clustering performance for manifold graphs.
arXiv Detail & Related papers (2021-12-15T03:45:39Z) - Algorithms and Hardness for Linear Algebra on Geometric Graphs [14.822517769254352]
We show that the exponential dependence on the dimension dimension $d in the celebrated fast multipole method of Greengard and Rokhlin cannot be improved.
This is the first formal limitation proven about fast multipole methods.
arXiv Detail & Related papers (2020-11-04T18:35:02Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.