Results 21 to 30 of about 32,516 (266)

Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [PDF]

, 2020
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De-quantizing such algorithms has received a flurry of attention in recent years; we obtain sharper bounds for these problems. More significantly, we achieve these improvements
Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh, David P. Woodruff, Woodruff, David P.   +4 more
openalex   +3 more sources

Randomized Linear Algebra Approaches to Estimate the Von Neumann Entropy of Density Matrices. [PDF]

IEEE Trans Inf Theory, 2020
Thevon Neumann entropy, named after John von Neumann, is an extension of the classical concept of entropy to the field of quantum mechanics. From a numerical perspective, von Neumann entropy can be computed simply by computing all eigenvalues of a density matrix, an operation that could be prohibitively expensive for large-scale density matrices.
Kontopoulou EM, Dexter GP, Szpankowski W, Grama A, Drineas P.   +4 more
europepmc   +5 more sources

Photonic co-processors in HPC: Using LightOn OPUs for Randomized Numerical Linear Algebra [PDF]

2021 IEEE Hot Chips 33 Symposium (HCS), 2021
Randomized Numerical Linear Algebra (RandNLA) is a powerful class of methods, widely used in High Performance Computing (HPC). RandNLA provides approximate solutions to linear algebra functions applied to large signals, at reduced computational costs.
Daniel Hesslow, Alessandro Cappelli, Igor Carron, Laurent Daudet, Raphaël Lafargue, Kilian Müller, Ruben Ohana, Gustave Pariente, Iacopo Poli   +8 more
openalex   +3 more sources

Random Process and Linear Algebra

Random Process and Linear Algebra is a comprehensive textbook that unifies two fundamental areas of mathematics and engineering, linear algebra and random processes, into a single cohesive resource. It provides a clear, structured, and application oriented approach that helps readers build both theoretical understanding and practical skills.
Dr. Md. Mushtaque Khan, Dr. Nasim Akhtar, Mr. Manoj Kumar, Dr. Jyoti Mishra, Dr. Md. Naushad   +4 more
  +4 more sources

Randomized numerical linear algebra: Foundations and algorithms [PDF]

Acta Numerica, 2020
This survey describes probabilistic algorithms for linear algebraic computations, such as factorizing matrices and solving linear systems. It focuses on techniques that have a proven track record for real-world problems. The paper treats both the theoretical foundations of the subject and practical computational issues.Topics include norm estimation ...
Martinsson, Per-Gunnar, Tropp, Joel A.
openaire   +3 more sources

Determinantal Point Processes in Randomized Numerical Linear Algebra

Notices of the American Mathematical Society, 2020
Randomized Numerical Linear Algebra (RandNLA) uses randomness to develop improved algorithms for matrix problems that arise in scientific computing, data science, machine learning, etc. Determinantal Point Processes (DPPs), a seemingly unrelated topic in pure and applied mathematics, is a class of stochastic point processes with probability ...
Michał Dereziński, Michael W. Mahoney
openalex   +3 more sources

Randomized Communication Complexity for Linear Algebra Problems over Finite Fields

, 2012
Finding the singularity of a matrix is a basic problem in linear algebra. Chu and Schnitger [SC95] first considered this problem in the communication complexity model, in which Alice holds the first half of the matrix and Bob holds the other half. They proved that the deterministic communication complexity is Omega(n^2 log p) for an n by n matrix over ...
Xiaoming Sun, Chengu Wang
openalex   +6 more sources

Qubit-Efficient Randomized Quantum Algorithms for Linear Algebra [PDF]

PRX Quantum
We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic and no additional qubits are required for quantum data structures.
Samson Wang, Sam McArdle, Mario Berta
openalex   +5 more sources

RANDOMIZED NUMERICAL LINEAR ALGEBRA APPROACHES FOR APPROXIMATING MATRIX FUNCTIONS

, 2020
This work explores how randomization can be exploited to deliver sophisticatedalgorithms with provable bounds for: (i) The approximation of matrix functions, suchas the log-determinant and the Von-Neumann entropy; and (ii) The low-rank approximationof matrices.
Evgenia-Maria Kontopoulou
openalex   +3 more sources

Bringing randomized algorithms to mainstream numerical linear algebra

Riley Murray
openalex   +2 more sources