The Experts below are selected from a list of 8721 Experts worldwide ranked by ideXlab platform
Tapio Pahikkala - One of the best experts on this subject based on the ideXlab platform.
-
Fast Kronecker Product Kernel Methods via Generalized Vec Trick
IEEE Transactions on Neural Networks and Learning Systems, 2018Co-Authors: Antti Airola, Tapio PahikkalaAbstract:Kronecker Product kernel provides the standard approach in the kernel methods' literature for learning from graph data, where edges are labeled and both start and end vertices have their own feature representations. The methods allow generalization to such new edges, whose start and end vertices do not appear in the training data, a setting known as zero-shot or zero-data learning. Such a setting occurs in numerous applications, including drug-target interaction prediction, collaborative filtering, and information retrieval. Efficient training algorithms based on the so-called vec trick that makes use of the special structure of the Kronecker Product are known for the case where the training data are a complete bipartite graph. In this paper, we generalize these results to noncomplete training graphs. This allows us to derive a general framework for training Kronecker Product kernel methods, as specific examples we implement Kronecker ridge regression and support vector machine algorithms. Experimental results demonstrate that the proposed approach leads to accurate models, while allowing order of magnitude improvements in training and prediction time.
-
fast Kronecker Product kernel methods via generalized vec trick
arXiv: Machine Learning, 2016Co-Authors: Antti Airola, Tapio PahikkalaAbstract:Kronecker Product kernel provides the standard approach in the kernel methods literature for learning from graph data, where edges are labeled and both start and end vertices have their own feature representations. The methods allow generalization to such new edges, whose start and end vertices do not appear in the training data, a setting known as zero-shot or zero-data learning. Such a setting occurs in numerous applications, including drug-target interaction prediction, collaborative filtering and information retrieval. Efficient training algorithms based on the so-called vec trick, that makes use of the special structure of the Kronecker Product, are known for the case where the training data is a complete bipartite graph. In this work we generalize these results to non-complete training graphs. This allows us to derive a general framework for training Kronecker Product kernel methods, as specific examples we implement Kronecker ridge regression and support vector machine algorithms. Experimental results demonstrate that the proposed approach leads to accurate models, while allowing order of magnitude improvements in training and prediction time.
David P. Woodruff - One of the best experts on this subject based on the ideXlab platform.
-
optimal sketching for Kronecker Product regression and low rank approximation
arXiv: Data Structures and Algorithms, 2019Co-Authors: Huaian Diao, Zhao Song, Wen Sun, Rajesh Jayaram, David P. WoodruffAbstract:We study the Kronecker Product regression problem, in which the design matrix is a Kronecker Product of two or more matrices. Given $A_i \in \mathbb{R}^{n_i \times d_i}$ for $i=1,2,\dots,q$ where $n_i \gg d_i$ for each $i$, and $b \in \mathbb{R}^{n_1 n_2 \cdots n_q}$, let $\mathcal{A} = A_1 \otimes A_2 \otimes \cdots \otimes A_q$. Then for $p \in [1,2]$, the goal is to find $x \in \mathbb{R}^{d_1 \cdots d_q}$ that approximately minimizes $\|\mathcal{A}x - b\|_p$. Recently, Diao, Song, Sun, and Woodruff (AISTATS, 2018) gave an algorithm which is faster than forming the Kronecker Product $\mathcal{A}$ Specifically, for $p=2$ their running time is $O(\sum_{i=1}^q \text{nnz}(A_i) + \text{nnz}(b))$, where nnz$(A_i)$ is the number of non-zero entries in $A_i$. Note that nnz$(b)$ can be as large as $n_1 \cdots n_q$. For $p=1,$ $q=2$ and $n_1 = n_2$, they achieve a worse bound of $O(n_1^{3/2} \text{poly}(d_1d_2) + \text{nnz}(b))$. In this work, we provide significantly faster algorithms. For $p=2$, our running time is $O(\sum_{i=1}^q \text{nnz}(A_i) )$, which has no dependence on nnz$(b)$. For $p<2$, our running time is $O(\sum_{i=1}^q \text{nnz}(A_i) + \text{nnz}(b))$, which matches the prior best running time for $p=2$. We also consider the related all-pairs regression problem, where given $A \in \mathbb{R}^{n \times d}, b \in \mathbb{R}^n$, we want to solve $\min_{x} \|\bar{A}x - \bar{b}\|_p$, where $\bar{A} \in \mathbb{R}^{n^2 \times d}, \bar{b} \in \mathbb{R}^{n^2}$ consist of all pairwise differences of the rows of $A,b$. We give an $O(\text{nnz}(A))$ time algorithm for $p \in[1,2]$, improving the $\Omega(n^2)$ time needed to form $\bar{A}$. Finally, we initiate the study of Kronecker Product low rank and low $t$-rank approximation. For input $\mathcal{A}$ as above, we give $O(\sum_{i=1}^q \text{nnz}(A_i))$ time algorithms, which is much faster than computing $\mathcal{A}$.
-
optimal sketching for Kronecker Product regression and low rank approximation
Neural Information Processing Systems, 2019Co-Authors: Huaian Diao, Zhao Song, Wen Sun, Rajesh Jayaram, David P. WoodruffAbstract:We study the Kronecker Product regression problem, in which the design matrix is a Kronecker Product of two or more matrices. Formally, given $A_i \in \R^{n_i \times d_i}$ for $i=1,2,\dots,q$ where $n_i \gg d_i$ for each $i$, and $b \in \R^{n_1 n_2 \cdots n_q}$, let $\mathcal{A} = A_i \otimes A_2 \otimes \cdots \otimes A_q$. Then for $p \in [1,2]$, the goal is to find $x \in \R^{d_1 \cdots d_q}$ that approximately minimizes $\|\mathcal{A}x - b\|_p$. Recently, Diao, Song, Sun, and Woodruff (AISTATS, 2018) gave an algorithm which is faster than forming the Kronecker Product $\mathcal{A} \in \R^{n_1 \cdots n_q \times d_1 \cdots d_q}$. Specifically, for $p=2$ they achieve a running time of $O(\sum_{i=1}^q \texttt{nnz}(A_i) + \texttt{nnz}(b))$, where $ \texttt{nnz}(A_i)$ is the number of non-zero entries in $A_i$. Note that $\texttt{nnz}(b)$ can be as large as $\Theta(n_1 \cdots n_q)$. For $p=1,$ $q=2$ and $n_1 = n_2$, they achieve a worse bound of $O(n_1^{3/2} \text{poly}(d_1d_2) + \texttt{nnz}(b))$. In this work, we provide significantly faster algorithms. For $p=2$, our running time is $O(\sum_{i=1}^q \texttt{nnz}(A_i) )$, which has no dependence on $\texttt{nnz}(b)$. For $p<2$, our running time is $O(\sum_{i=1}^q \texttt{nnz}(A_i) + \texttt{nnz}(b))$, which matches the prior best running time for $p=2$. We also consider the related all-pairs regression problem, where given $A \in \R^{n \times d}, b \in \R^n$, we want to solve $\min_{x \in \R^d} \|\bar{A}x - \bar{b}\|_p$, where $\bar{A} \in \R^{n^2 \times d}, \bar{b} \in \R^{n^2}$ consist of all pairwise differences of the rows of $A,b$. We give an $O(\texttt{nnz}(A))$ time algorithm for $p \in[1,2]$, improving the $\Omega(n^2)$ time required to form $\bar{A}$. Finally, we initiate the study of Kronecker Product low rank and and low-trank approximation. For input $\mathcal{A}$ as above, we give $O(\sum_{i=1}^q \texttt{nnz}(A_i))$ time algorithms, which is much faster than computing $\mathcal{A}$.
-
Sketching for Kronecker Product Regression and P-splines
arXiv: Data Structures and Algorithms, 2017Co-Authors: Huaian Diao, Zhao Song, Wen Sun, David P. WoodruffAbstract:TensorSketch is an oblivious linear sketch introduced in Pagh'13 and later used in Pham, Pagh'13 in the context of SVMs for polynomial kernels. It was shown in Avron, Nguyen, Woodruff'14 that TensorSketch provides a subspace embedding, and therefore can be used for canonical correlation analysis, low rank approximation, and principal component regression for the polynomial kernel. We take TensorSketch outside of the context of polynomials kernels, and show its utility in applications in which the underlying design matrix is a Kronecker Product of smaller matrices. This allows us to solve Kronecker Product regression and non-negative Kronecker Product regression, as well as regularized spline regression. Our main technical result is then in extending TensorSketch to other norms. That is, TensorSketch only provides input sparsity time for Kronecker Product regression with respect to the $2$-norm. We show how to solve Kronecker Product regression with respect to the $1$-norm in time sublinear in the time required for computing the Kronecker Product, as well as for more general $p$-norms.
Jingdong Chen - One of the best experts on this subject based on the ideXlab platform.
-
on the design of flexible Kronecker Product beamformers with linear microphone arrays
International Conference on Acoustics Speech and Signal Processing, 2019Co-Authors: Wenxing Yang, Israel Cohen, Jacob Benesty, Gongping Huang, Jingdong ChenAbstract:This paper proposes a method for the design of flexible Kronecker Product beamformers based on the decomposition of the steering vector of a physical array as a Kronecker Product of steering vectors of two smaller virtual arrays. With this decomposition, the global beamforming filter is designed by optimizing the two sub-beamformers in a cascaded manner, which can offer much flexibility to control the performance of beamforming or control the compromise between different, conflicted performance measures. In comparison with a recently developed method that restricts the number of microphones of the given physical array to a multiplication of two integers, each corresponding to the number of sensors of one virtual array, the approach in this work decomposes the physical array in such a way that the sensors in the two virtual arrays may share positions and the number of microphones of the physical array can be any positive integer. Simulations demonstrate the properties of the proposed approach.
-
Differential Kronecker Product Beamforming
IEEE ACM Transactions on Audio Speech and Language Processing, 2019Co-Authors: Israel Cohen, Jacob Benesty, Jingdong ChenAbstract:Differential beamformers have attracted much interest over the past few decades. In this paper, we introduce differential Kronecker Product beamformers that exploit the structure of the steering vector to perform beamforming differently from the well-known and studied conventional approach. We consider a class of microphone arrays that enable to decompose the steering vector as a Kronecker Product of two steering vectors of smaller virtual arrays. In the proposed approach, instead of directly designing the differential beamformer, we break it down following the decomposition of the steering vector, and show how to derive differential beamformers using the Kronecker Product formulation. As demonstrated, the Kronecker Product decomposition facilitates further flexibility in the design of differential beamformers and in the tradeoff control between the directivity factor and the white noise gain.
Alfred O Hero - One of the best experts on this subject based on the ideXlab platform.
-
covariance estimation in high dimensions via Kronecker Product expansions
IEEE Transactions on Signal Processing, 2013Co-Authors: Theodoros Tsiligkaridis, Alfred O HeroAbstract:This paper presents a new method for estimating high dimensional covariance matrices. The method, permuted rank-penalized least-squares (PRLS), is based on a Kronecker Product series expansion of the true covariance matrix. Assuming an i.i.d. Gaussian random sample, we establish high dimensional rates of convergence to the true covariance as both the number of samples and the number of variables go to infinity. For covariance matrices of low separation rank, our results establish that PRLS has significantly faster convergence than the standard sample covariance matrix (SCM) estimator. The convergence rate captures a fundamental tradeoff between estimation error and approximation error, thus providing a scalable covariance estimation framework in terms of separation rank, similar to low rank approximation of covariance matrices . The MSE convergence rates generalize the high dimensional rates recently obtained for the ML Flip-flop algorithm , for Kronecker Product covariance estimation. We show that a class of block Toeplitz covariance matrices is approximatable by low separation rank and give bounds on the minimal separation rank r that ensures a given level of bias. Simulations are presented to validate the theoretical bounds. As a real world application, we illustrate the utility of the proposed Kronecker covariance estimator for spatio-temporal linear least squares prediction of multivariate wind speed measurements.
Antti Airola - One of the best experts on this subject based on the ideXlab platform.
-
Fast Kronecker Product Kernel Methods via Generalized Vec Trick
IEEE Transactions on Neural Networks and Learning Systems, 2018Co-Authors: Antti Airola, Tapio PahikkalaAbstract:Kronecker Product kernel provides the standard approach in the kernel methods' literature for learning from graph data, where edges are labeled and both start and end vertices have their own feature representations. The methods allow generalization to such new edges, whose start and end vertices do not appear in the training data, a setting known as zero-shot or zero-data learning. Such a setting occurs in numerous applications, including drug-target interaction prediction, collaborative filtering, and information retrieval. Efficient training algorithms based on the so-called vec trick that makes use of the special structure of the Kronecker Product are known for the case where the training data are a complete bipartite graph. In this paper, we generalize these results to noncomplete training graphs. This allows us to derive a general framework for training Kronecker Product kernel methods, as specific examples we implement Kronecker ridge regression and support vector machine algorithms. Experimental results demonstrate that the proposed approach leads to accurate models, while allowing order of magnitude improvements in training and prediction time.
-
fast Kronecker Product kernel methods via generalized vec trick
arXiv: Machine Learning, 2016Co-Authors: Antti Airola, Tapio PahikkalaAbstract:Kronecker Product kernel provides the standard approach in the kernel methods literature for learning from graph data, where edges are labeled and both start and end vertices have their own feature representations. The methods allow generalization to such new edges, whose start and end vertices do not appear in the training data, a setting known as zero-shot or zero-data learning. Such a setting occurs in numerous applications, including drug-target interaction prediction, collaborative filtering and information retrieval. Efficient training algorithms based on the so-called vec trick, that makes use of the special structure of the Kronecker Product, are known for the case where the training data is a complete bipartite graph. In this work we generalize these results to non-complete training graphs. This allows us to derive a general framework for training Kronecker Product kernel methods, as specific examples we implement Kronecker ridge regression and support vector machine algorithms. Experimental results demonstrate that the proposed approach leads to accurate models, while allowing order of magnitude improvements in training and prediction time.
