A Maximum Matching Algorithm for Basis Selection in Spectral Learning
We present a solution to scale spectral algorithms for learning sequence functions. We are interested in the case where these functions are sparse (that is, for most sequences they return 0). Spectral algorithms reduce the learning problem to the task of computing an SVD decomposition over a special type of matrix called the Hankel matrix. This matrix is designed to capture the relevant statistics of the training sequences. What is crucial is that to capture long range dependencies we must consider very large Hankel matrices. Thus the computation of the SVD becomes a critical bottleneck. Our solution finds a subset of rows and columns of the Hankel that realizes a compact and informative Hankel submatrix. The novelty lies in the way that this subset is selected: we exploit a maximal bipartite matching combinatorial algorithm to look for a sub-block with full structural rank, and show how computation of this sub-block can be further improved by exploiting the specific structure of Hankel matrices.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
From Feature Learning to Spectral Basis Learning: A Unifying and Flexible Framework for Efficient and Robust Shape Matching
Shape matching is a fundamental task in computer graphics and vision, with deep functional maps becoming a prominent paradigm. However, existing methods primarily focus on learning informative feature representations by …
Technical Report: Band selection for nonlinear unmixing of hyperspectral images as a maximal clique problem
Kernel-based nonlinear mixing models have been applied to unmix spectral information of hyperspectral images when the type of mixing occurring in the scene is too complex or unknown. Such methods, however, usually requir…
Portfolio Selection with Multiple Spectral Risk Constraints
We propose an iterative gradient-based algorithm to efficiently solve the portfolio selection problem with multiple spectral risk constraints. Since the conditional value at risk (CVaR) is a special case of the spectral …
Sample selection from a given dataset to validate machine learning models
The selection of a validation basis from a full dataset is often required in industrial use of supervised machine learning algorithm. This validation basis will serve to realize an independent evaluation of the machine l…
BIG-bench Machine LearningA Directed Graph Fourier Transform with Spread Frequency Components
We study the problem of constructing a graph Fourier transform (GFT) for directed graphs (digraphs), which decomposes graph signals into different modes of variation with respect to the underlying network. Accordingly, t…
Denoising