Search

The present work is devoted to the eigenvalue asymptotic expansion of the Toeplitz matrix Tn(a), whose generating function a is complex-valued and has a power singularity at one point. As a consequence, Tn(a) is non-Hermitian and we know that in this setting, the eigenvalue computation is a nontrivial task for large sizes. First we follow the work of Bogoya, Böttcher, Grudsky, and Maximenko and deduce a complete asymptotic expansion for the eigenvalues. In a second step, we apply matrixless algorithms, in the spirit of the work by Ekström, Furci, Garoni, Serra-Capizzano et al., for computing those eigenvalues. Since the inner and extreme eigenvalues have different asymptotic behaviors, we worked on them independently and combined the results to produce a high precision global numerical and matrixless algorithm. The numerical results are very precise, and the computational cost of the proposed algorithms is independent of the size of the considered matrices for each eigenvalue, which implies a linear cost when the entire spectrum is computed. From the viewpoint of real-world applications, we emphasize that the class under consideration includes the matrices stemming from the numerical approximation of fractional diffusion equations. In the final section a concise discussion on the matter and a few open problems are presented. [ABSTRACT FROM AUTHOR]

In this paper new general modewise Johnson--Lindenstrauss (JL) subspace embeddings are proposed that can be both generated much faster and stored more easily than traditional JL embeddings when working with extremely large vectors and/or tensors. Corresponding embedding results are then proven for two different types of low-dimensional (tensor) subspaces. The first of these new subspace embedding results produces improved space complexity bounds for embeddings of rank-r tensors whose CP decompositions are contained in the span of a fixed (but unknown) set of r rank-1 basis tensors. In the traditional vector setting this first result yields new and very general near-optimal oblivious subspace embedding constructions that require fewer random bits to generate than standard JL embeddings when embedding subspaces of

We introduce a fast algorithm for entrywise evaluation of the Gauss--Newton Hessian (GNH) matrix for the fully connected feed-forward neural network. The algorithm has a precomputation step and a sampling step. While it generally requires O(Nri) work to compute an entry (and the entire column) in the GNH matrix for a neural network with N parameters and n data points, our fast sampling algorithm reduces the cost to O(n + d/e²) work, where d is the output dimension of the network and e is a prescribed accuracy (independent of N). One application of our algorithm is constructing the hierarchical-matrix (H-matrix) approximation of the GNH matrix for solving linear systems and eigenvalue problems. It generally requires O(N²) memory and O(N³) work to store and factorize the GNH matrix, respectively. The 'H-matrix approximation requires only O(Nro) memory footprint and O(Nr°) work to be factorized, where ro O N is the maximum rank of off-diagonal blocks in the GNH matrix. We demonstrate the performance of our fast algorithm and the H-matrix approximation on classification and autoencoder neural networks. [ABSTRACT FROM AUTHOR]

Kernel methods are widespread in machine learning; however, they are limited by the quadratic complexity of the construction, application, and storage of kernel matrices. Low-rank matrix approximation algorithms are widely used to address this problem and reduce the arithmetic and storage cost. However, we observed that for some datasets with wide intraclass variability, the optimal kernel parameter for smaller classes yields a matrix that is less well-approximated by low-rank methods. In this paper, we propose an efficient structured low-rank approximation method|the block basis factorization (BBF)|and its fast construction algorithm to approximate radial basis function kernel matrices. Our approach has linear memory cost and oating point operations for many machine learning kernels. BBF works for a wide range of kernel bandwidth parameters and extends the domain of applicability of low-rank approximation methods significantly. Our empirical results demonstrate the stability and superiority over the state-of-the-art kernel approximation algorithms. [ABSTRACT FROM AUTHOR]

Randomized algorithms for low-rank matrix approximation are investigated, with the emphasis on the fixed-precision problem and computational efficiency for handling large matrices. The algorithms are based on the so-called QB factorization, where Q is an orthonormal matrix. First, a mechanism for calculating the approximation error in the Frobenius norm is proposed, which enables efficient adaptive rank determination for a large and/or sparse matrix. It can be combined with any QB-form factorization algorithm in which B's rows are incrementally generated. Based on the blocked randQB algorithm by Martinsson and Voronin, this results in an algorithm called randQB EI. Then, we further revise the algorithm to obtain a pass-efficient algorithm, randQB FP, which is mathematically equivalent to the existing randQB algorithms and also suitable for the fixed-precision problem. Especially, randQB FP can serve as a single-pass algorithm for calculating leading singular values, under a certain condition. With large and/or sparse test matrices, we have empirically validated the merits of the proposed techniques, which exhibit remarkable speedup and memory saving over the blocked randQB algorithm. We have also demonstrated that the single-pass algorithm derived by randQB FP is much more accurate than an existing single-pass algorithm. And with data from a scenic image and an information retrieval application, we have shown the advantages of the proposed algorithms over the adaptive range finder algorithm for solving the fixed-precision problem. [ABSTRACT FROM AUTHOR]

Recently it was shown how necessary and sufficient information for solving an orthogonally invariant linear approximation problem AX ≈ B with multiple right-hand sides can be revealed through the so-called core problem reduction; see [I. Hnětynková, M. Plešinger, and Z. Strakoš, SIAM J. Matrix Anal. Appl., 34 (2013), pp. 917-931]. The total least squares (TLS) serves as an important example of such approximation problem. Solvability of TLS was discussed in the full generality in [I. Hnětynková et al., SIAM J. Matrix Anal. Appl., 32 (2011), pp. 748-770]. This theoretical study investigates solvability of core problems with multiple right-hand sides in the TLS sense. It is shown that, contrary to the single right-hand side case, a core problem with multiple right-hand sides may not have a TLS solution. Further possible internal structure of core problems is studied. Outputs of the classical TLS algorithm for the original problem AX ≈ B and for the core problem within AX ≈ B are compared. [ABSTRACT FROM AUTHOR]

The need to compute small con-eigenvalues and the associated con-eigenvectors of positive-definite Cauchy matrices naturally arises when constructing rational approximations with a (near) optimally small L∞ error. Specifically, given a rational function with n poles in the unit disk, a rational approximation with m << n poles in the unit disk may be obtained from the mth con-eigenvector of an n x n Cauchy matrix, where the associated con-eigenvalue λm > 0 gives the approximation error in the L∞ norm. Unfortunately, standard algorithms do not accurately compute small con-eigenvalues (and the associated con-eigenvectors) and, in particular, yield few or no correct digits for con-eigenvalues smaller than the machine roundoff. We develop a fast and accurate algorithm for computing con-eigenvalues and con-eigenvectors of positive-definite Cauchy matrices, yielding even the tiniest con-eigenvalues with high relative accuracy. The algorithm computes the mth con-eigenvalue in O(m²n) operations and, since the con-eigenvalues of positive-definite Cauchy matrices decay exponentially fast, we obtain (near) optimal rational approximations in O(n (log δ-1)²) operations, where δ is the approximation error in the L∞ norm. We provide error bounds demonstrating high relative accuracy of the computed con-eigenvalues and the high accuracy of the unit con-eigenvectors. We also provide examples of using the algorithm to compute (near) optimal rational approximations of functions with singularities and sharp transitions, where approximation errors close to machine roundoff are obtained. Finally, we present numerical tests on random (complex-valued) Cauchy matrices to show that the algorithm computes all the con-eigenvalues and con-eigenvectors with nearly full precision. [ABSTRACT FROM AUTHOR]

We present a general class of compressed sensing matrices which are then demonstrated to have associated sublinear-time sparse approximation algorithms. We then develop methods for constructing specialized matrices from this class which are sparse when multiplied with a discrete Fourier transform matrix. Ultimately, these considerations improve previous sampling requirements for deterministic sparse Fourier transform methods. [ABSTRACT FROM AUTHOR]