A Multilevel Monte Carlo Estimator for Matrix Multiplication

Yue Wu; Nick Polydorides

doi:10.1137/19M125604X

A Multilevel Monte Carlo Estimator for Matrix Multiplication

Yue Wu, Nick Polydorides

School of Engineering

Research output: Contribution to journal › Article › peer-review

Abstract / Description of output

Inspired by recent developments in multilevel Monte Carlo (MLMC) methods and randomised sketching for linear algebra problems we propose a MLMC estimator for real-time processing of matrix structured random data. Our algorithm is particularly effective in handling high-dimensional inner products and matrix multiplication, and finds applications in computer vision and large-scale supervised learning.

Original language	English
Pages (from-to)	A2731-A2749
Number of pages	19
Journal	SIAM Journal on Scientific Computing
Volume	42
Issue number	5
DOIs	https://doi.org/10.1137/19M125604X
Publication status	Published - 15 Sept 2020

Keywords / Materials (for Non-textual outputs)

randomised sampling
sketching
Machine Learning

Access to Document

10.1137/19M125604XLicence: All Rights Reserved

main_siamsc_acceptedAccepted author manuscript, 405 KB

https://arxiv.org/abs/1904.00429

Cite this

@article{a9aeed9128ba4d3f8742bf5607354f7d,

title = "A Multilevel Monte Carlo Estimator for Matrix Multiplication",

abstract = "Inspired by recent developments in multilevel Monte Carlo (MLMC) methods and randomised sketching for linear algebra problems we propose a MLMC estimator for real-time processing of matrix structured random data. Our algorithm is particularly effective in handling high-dimensional inner products and matrix multiplication, and finds applications in computer vision and large-scale supervised learning.",

keywords = "randomised sampling, sketching, Machine Learning",

author = "Yue Wu and Nick Polydorides",

year = "2020",

month = sep,

day = "15",

doi = "10.1137/19M125604X",

language = "English",

volume = "42",

pages = "A2731--A2749",

journal = "SIAM Journal on Scientific Computing",

issn = "1064-8275",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "5",

}

TY - JOUR

T1 - A Multilevel Monte Carlo Estimator for Matrix Multiplication

AU - Wu, Yue

AU - Polydorides, Nick

PY - 2020/9/15

Y1 - 2020/9/15

N2 - Inspired by recent developments in multilevel Monte Carlo (MLMC) methods and randomised sketching for linear algebra problems we propose a MLMC estimator for real-time processing of matrix structured random data. Our algorithm is particularly effective in handling high-dimensional inner products and matrix multiplication, and finds applications in computer vision and large-scale supervised learning.

AB - Inspired by recent developments in multilevel Monte Carlo (MLMC) methods and randomised sketching for linear algebra problems we propose a MLMC estimator for real-time processing of matrix structured random data. Our algorithm is particularly effective in handling high-dimensional inner products and matrix multiplication, and finds applications in computer vision and large-scale supervised learning.

KW - randomised sampling

KW - sketching

KW - Machine Learning

UR - https://ora.ox.ac.uk/objects/uuid:4e4c2699-26dc-44f2-aef2-c41e1b5b68b0

U2 - 10.1137/19M125604X

DO - 10.1137/19M125604X

M3 - Article

SN - 1064-8275

VL - 42

SP - A2731-A2749

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

IS - 5

ER -

A Multilevel Monte Carlo Estimator for Matrix Multiplication

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Other files and links

Fingerprint

Randomness: A Resource for Real-Time Analytics

Cite this

A Multilevel Monte Carlo Estimator for Matrix Multiplication

Abstract / Description of output

Keywords / Materials (for Non-textual outputs)

Access to Document

Other files and links

Fingerprint

Projects

Randomness: A Resource for Real-Time Analytics

Cite this