ML p(r)ior | Efficiently Correcting Matrix Products

Efficiently Correcting Matrix Products

2016-02-01
We study the problem of efficiently correcting an erroneous product of two $n\times n$ matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most $k$ erroneous entries running in $\tilde{O}(n^2+kn)$ time and a deterministic $\tilde{O}(kn^2)$-time algorithm for this problem (where the notation $\tilde{O}$ suppresses polylogarithmic terms in $n$ and $k$).
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2012-04-09
1204.1956 | cs.LG

Topic Modeling is an approach used for automatic comprehension and classification of data in a varie… show more
PDF

Highlights - Most important sentences from the article

2014-10-14

In this work, we propose a new randomized algorithm for computing a low-rank approximation to a give… show more
PDF

Highlights - Most important sentences from the article

2016-10-21

In this paper we present a new algorithm for computing a low rank approximation of the product $A^TB… show more
PDF

Highlights - Most important sentences from the article

2019-05-05

Distributed processing frameworks, such as MapReduce, Hadoop, and Spark are popular systems for proc… show more
PDF

Highlights - Most important sentences from the article

2019-03-07
1903.02742 | cs.DS

We consider the extensively studied problem of $\ell_2/\ell_2$ compressed sensing. The main contribu… show more
PDF

Highlights - Most important sentences from the article

2018-09-19
1809.06986 | cs.DS

Let $\mathbf{P}=\{ p_1, p_2, \ldots p_n \}$ and $\mathbf{Q} = \{ q_1, q_2 \ldots q_m \}$ be two poin… show more
PDF

Highlights - Most important sentences from the article

2019-05-13

The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and col… show more
PDF

Highlights - Most important sentences from the article

2018-11-12

We present classical sublinear-time algorithms for solving low-rank linear systems of equations. Our… show more
PDF

Highlights - Most important sentences from the article

2019-01-09
1901.02852 | cs.IT

Construction of error-correcting codes achieving a designated minimum distance parameter is a centra… show more
PDF

Highlights - Most important sentences from the article

2018-06-10
1806.03701 | cs.DS

There have been several algorithms designed to optimise matrix multiplication. From schoolbook metho… show more
PDF

Highlights - Most important sentences from the article

2018-11-03

We consider the ILP Feasibility problem: given an integer linear program $\{Ax = b, x\geq 0\}$, wher… show more
PDF

Highlights - Most important sentences from the article

2018-04-06

Simulating the time-evolution of quantum mechanical systems is BQP-hard and expected to be one of th… show more
PDF

Highlights - Most important sentences from the article

2017-04-13

Understanding the singular value spectrum of a matrix $A \in \mathbb{R}^{n \times n}$ is a fundament… show more
PDF

Highlights - Most important sentences from the article

2017-04-11
1704.03371 | cs.DS

We show how to compute a relative-error low-rank approximation to any positive semidefinite (PSD) ma… show more
PDF

Highlights - Most important sentences from the article

2017-12-20

We consider non-adaptive threshold group testing for identification of up to $d$ defective items in … show more
PDF

Highlights - Most important sentences from the article

2017-10-30

We study the $\ell_0$-Low Rank Approximation Problem, where the goal is, given an $m \times n$ matri… show more
PDF

Highlights - Most important sentences from the article