Automatically learns efficient algorithms for structured transforms like FFT.
problem Efficient algorithms for structured linear transforms.
method Generic parameterization of divide-and-conquer methods.
result Reproduces Cooley-Tukey FFT algorithm to machine precision.
Efficient algorithm finds fast Transformer models.
problem Slow inference time of Transformer models.
method Decompose Transformer architecture into components, use sampling-based one-shot search.
result Achieved 10% to 30% speedup on pre-trained BERT and 70% on top of a previous state-of-the-art model.
Paper presents a fast algorithm for pricing Bermudan swaptions under the two-factor Hull-White model.
problem Evaluating Bermudan swaption prices under the two-factor Hull-White model with high computational efficiency.
method Discretization of expected value calculation, Gaussian kernel sums, fast Gauss transform, grid rotation for stability.
result Significant reduction in computation time and improved stability for correlation close to -1.
This paper develops fast orthonormal dictionaries using Householder reflectors.
problem Learning sparse representations with non-convex and computationally complex dictionaries.
method Develops orthonormal dictionaries from products of Householder reflectors, proposing sequential and simultaneous update algorithms.
result Proposed algorithms achieve low computational complexity and converge to local minimum points.
Efficiently calculates Brazilian stock options with discrete dividends.
problem Accurately pricing Brazilian listed equity options with discrete dividends.
method Uses the fast Laplace transform for high-accuracy computation.
result Efficiently computes option premiums and Greeks with high accuracy.
A new algorithm computes Fourier coefficients for a specified range efficiently.
problem Inefficiency in FFT due to fixed output size for all applications.
method Fast Partial Fourier Transform (PFT) that allows specifying the range of Fourier coefficients to compute.
result PFT achieves significant speedup over state-of-the-art FFT algorithms for small output sizes.
Analytical pricing formulas and Greeks are obtained for European and American basket put options using Mellin transforms. We assume assets are driven by geometric Brownian motion which exhibit correlation and pay a continuous dividend rate. A novel approach to numerical Mellin inversion is achieved via the fast Fourier…
The paper calculates option prices for assets with stochastic volatility using FFT.
problem Calculating option prices for assets with stochastic volatility.
method Assumed normal asset dynamics with stochastic volatility following CIR process. Used FFT for evaluation and compared with Monte Carlo simulation.
result Comparison of FFT and Monte Carlo results for option pricing.
MultiRocket boosts TSC speed and accuracy with pooling and transformations.
problem Efficient time series classification with high accuracy.
method Multiple pooling operators and transformations applied to raw and differenced series.
result MultiRocket outperforms MiniRocket and is competitive with state-of-the-art methods in terms of accuracy and speed.
A new NUFFT method speeds up option pricing for various strikes.
problem Efficiently pricing many options of the same maturity but different strikes.
method Non-uniform fast Fourier transform (NUFFT) applied to the COS method.
result Significantly faster computation of option prices.
Efficient trainable front-end for neural speech enhancement.
problem Inefficient STFT front-ends in neural speech enhancement models.
method Butterfly mechanism for Fast Fourier Transform, trainable STFT window.
result Accuracy and efficiency improvements for low-compute systems.
This paper introduces Haar convolution for GNNs to reduce computational cost.
problem High computational cost in GNNs for large graph sizes.
method Introduces Haar basis for graph convolution and Fast Haar Transforms.
result State-of-the-art results on graph-based regression and node classification tasks.
Kernel density estimation (KDE) is a popular statistical technique for estimating the underlying density distribution with minimal assumptions. Although they can be shown to achieve asymptotic estimation optimality for any input distribution, cross-validating for an optimal parameter requires significant computation do…
Efficiently approximates eigenspaces for symmetric and general matrices.
problem Fast computation of eigenspaces for large matrices.
method Factor eigenspaces into fundamental components using transformations, solve minimization problems, and iteratively update.
result Improved computational efficiency for eigenspace approximation.
The paper proposes efficient dictionary learning algorithms that avoid multiplications for sparse representations.
problem Sparse representation with reduced computational complexity.
method Factorizations of the dictionary into binary orthonormal, scaling, and shear transformations with closed-form solutions.
result The proposed methods are effective and can be compared to well-known transforms like FFT and DCT.
Enhances Fourier estimator performance for asynchronous event-data.
problem Improving correlation and covariance estimation on event-data.
method Implement and test NUFFT methods with different averaging kernels.
result Demonstrates improved performance and relationship between averaging scales.
We provide fast algorithms for overconstrained ℓp regression and related problems: for an n×d input matrix A and vector b∈Rn, in O(ndlogn) time we reduce the problem minx∈Rd∥Ax−b∥p to the same problem with input matrix A~ of dimension s×d and corr…
Paper introduces efficient orthonormal transformations using Householder reflectors.
problem Fast numerical procedures for orthonormal transformations are computationally expensive.
method Develops orthonormal matrices using Householder reflectors to approximate any orthonormal or symmetric transform.
result Approximations of orthonormal or symmetric transforms using a few Householder reflectors are accurate and computationally efficient.
We present an explicit example of a fast decaying solution to the modified Novikov--Veselov equation with a one-point singularity in the space-time. It is constructed by using the geometrical interpretation of the Moutard transformation of solutions to this equation and the Enneper minimal surface.
Fast approximates orthogonal matrices for PCA.
problem Approximating orthogonal matrices for fast computation.
method Optimization over structured matrices and greedy algorithm.
result Efficient approximation balances accuracy and speed.
Efficiently accelerates attention calculation for Transformers with relative positional encoding.
problem Quadratic complexity of attention in long sequences.
method Kernelized attention with Fast Fourier Transform (FFT) for RPE.
result Achieves O(n log n) time complexity, mitigates training instability, and outperforms other models.
Transformers with linear space and time complexity for accurate attention estimation.
problem Efficiently estimating attention in large-scale tasks without relying on priors.
method Performers use Fast Attention Via positive Orthogonal Random features (FAVOR+) for linear approximation of softmax attention.
result Performers achieve competitive results on various tasks, demonstrating the effectiveness of their attention-learning approach.
This work studies clustering in transformer models, proving exponential convergence to a single token state.
problem Understanding the long-term behavior of tokens in transformer models.
method Investigates mean-field transformer models under specific conditions to prove exponential convergence to a single state.
result Transformer models synchronize exponentially fast to a single token state with explicit rates.
New Performer model tackles long-sequence protein modeling.
problem Challenges of training complex Transformer models for long sequences.
method Linearly scalable long-context Transformer architecture, Performer.
result Performer provides strong theoretical guarantees and is effective for protein sequence modeling.
In this paper, we study a fast approximation method for {\it large-scale high-dimensional} sparse least-squares regression problem by exploiting the Johnson-Lindenstrauss (JL) transforms, which embed a set of high-dimensional vectors into a low-dimensional space. In particular, we propose to apply the JL transforms to …
New algorithm reduces dictionary learning complexity.
problem Efficiently learning dictionaries from high-dimensional data.
method IcTKM algorithm using dimensionality reduction and fast Fourier transform.
result Locally recovers dictionary with high probability.
Deep networks struggle to learn efficient representations of simple functions.
problem Can deep learning methods find efficient representations of simple functions?
method Trained deep neural networks on the parity function and fast Fourier transform, using gradient-based optimization.
result Deep networks require initialization close to exact solutions to learn efficient representations of simple functions.
Probabilistic inference procedures are usually coded painstakingly from scratch, for each target model and each inference algorithm. We reduce this effort by generating inference procedures from models automatically. We make this code generation modular by decomposing inference algorithms into reusable program-to-progr…
FIt-SNE accelerates t-SNE for large datasets.
problem Slow computation of t-SNE for large datasets.
method Interpolation-based t-SNE (FIt-SNE) using FFT and oocPCA.
result Significant acceleration of t-SNE computation for large datasets.
A hybrid framework uses machine learning to price options faster and more accurately.
problem Rapid recalibration of option pricing models in dynamic markets.
method Integrates smooth offset algorithm with supervised machine learning models.
result Surrogate pricing operators achieve up to 1000x speedup over direct SOA evaluation.
A fast calibration method for rough volatility models with jumps.
problem Calibrating stochastic volatility models to market data efficiently.
method Structure-preserving approach: split pricing formula, precompute data-independent integrals, and approximate market-dependent remainder with neural networks.
result Calibration achieves high accuracy and speed, and a pure-jump rough volatility model adequately captures VIX dynamics.
We illustrate how to compute local risk minimization (LRM) of call options for exponential Lévy models. We have previously obtained a representation of LRM for call options; here we transform it into a form that allows use of the fast Fourier transform method suggested by Carr & Madan. In particular, we consider Merton…
We derive the explicit formula for the joint Laplace transform of the Wishart process and its time integral which extends the original approach of Bru. We compare our methodology with the alternative results given by the variation of constants method, the linearization of the Matrix Riccati ODE's and the Runge-Kutta al…
A simple gating mechanism improves deep learning convergence.
problem Vanishing or exploding gradients in deep networks.
method Introducing a zero-initialized parameter to each residual connection.
result Training deep networks (up to 120 layers) with fast convergence and better performance.
Scalable kernel methods for large datasets using Fourier representations and NUFFT.
problem Cubic complexity in kernel methods limits their use on large-scale datasets.
method Fourier representation of kernels combined with NUFFT for O(n log n) complexity.
result Achieves minimax convergence rates and processes up to tens of billions of samples.
We address the problem of parameter estimation for diffusion driven stochastic volatility models through Markov chain Monte Carlo (MCMC). To avoid degeneracy issues we introduce an innovative reparametrisation defined through transformations that operate on the time scale of the diffusion. A novel MCMC scheme which ove…
Transformers become faster by linearizing self-attention.
problem Quadratic complexity of transformers makes them slow for long sequences.
method Expressed self-attention as a linear dot-product and used matrix product associativity to reduce complexity.
result Linear transformers are up to 4000x faster on long sequences.
New deep learning model estimates scattering timescale of FRBs efficiently.
problem Estimating scattering timescale of fast radio bursts (FRBs) is a bottleneck.
method Multimodal Transformer Based Generic Mixture Density Network (MT-GMDN) that ingests dynamic spectrum and timeseries profile.
result Achieves 94% R2 on expected value of τ for measurable scattering. GWNN uses graph wavelets for efficient graph CNNs.
problem Spectral graph CNNs' high computational cost and lack of interpretability.
method Graph wavelet transform for efficient graph convolution.
result GWNN significantly outperforms spectral graph CNNs.
A new fast method simulates stochastic volatility models.
problem Simulating stochastic volatility models efficiently.
method Karhunen-Loève expansions to express stochastic volatility as sine series, followed by analytical derivation of integrals.
result Simulation is several hundred times faster than existing methods.
Fast object detection in JPEG images without decompression.
problem Efficient object detection in compressed JPEG images.
method Modified SSD with DCT coefficients input processing.
result 2x faster detection with promising performance.
TensorFlow Distributions simplifies deep learning with flexible probability tools.
problem Creating efficient and flexible probability models for deep learning.
method Two basic abstractions (Distributions and Bijectors) for fast, differentiable computation.
result Modular construction of complex distributions and transformations.
Study efficient pricing for barrier options in stochastic-volatility models with leverage correction.
problem Barrier options are sensitive to volatility dynamics, especially leverage, making accurate pricing difficult.
method Developed a class of continuous-path stochastic-clock volatility models and a systematic small-ρ expansion to incorporate leverage.
result Transform-only pricing formulas for barrier derivatives are fast and numerically stable, even for negative leverage.
In this paper we consider Fourier transform techniques to efficiently compute the Value-at-Risk and the Conditional Value-at-Risk of an arbitrary loss random variable, characterized by having a computable generalized characteristic function. We exploit the property of these risk measures of being the solution of an ele…
FROCC uses random projections for fast one-class classification.
problem Efficient one-class classification for large datasets.
method Random projection of data onto random unit vectors, with region bounding.
result Significant improvement in ROC performance with substantial speedup.
The paper provides VIX option pricing and hedging strategies for two stochastic volatility models.
problem Pricing and hedging of VIX options for specific stochastic volatility models.
method Develops representations of VIX call option prices and locally risk-minimizing strategies for Barndorff-Nielsen and Shephard models.
result Efficient representations and locally risk-minimizing strategies for numerical methods.
A fast method learns plasma collision kernels from simulations, improving kinetic models.
problem Improving kinetic models for plasma dynamics beyond the weakly coupled regime.
method Data-driven collisional operator, fast spectral separation method.
result Accurately captures plasma dynamics in moderately coupled regime.
Adaptive GMRA approximates high-dimensional data with low-dimensional geometric structures.
problem Efficiently approximating high-dimensional data from a nearly low-dimensional manifold.
method Adaptive GMRA with thresholding of geometric wavelet coefficients.
result Adaptive GMRA approximations perform well on various measures with different regularity.