### Efficiently Correcting Matrix Products

**2016-02-01**

1602.00435 | cs.DS

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$).

**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

**2014-10-14**

1410.3886 | cs.DS

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

**2016-10-21**

1610.06656 | stat.ML

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

**2019-05-05**

1905.01748 | cs.DS

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

**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

**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

**2019-05-13**

1905.05067 | cs.DS

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

**2018-11-12**

1811.04852 | cs.DS

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

**2019-01-09**

1901.02852 | cs.IT

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

**2018-06-10**

1806.03701 | cs.DS

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

**2018-11-03**

1811.01296 | cs.DS

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

**2018-04-06**

1804.02484 | quant-ph

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

**2017-04-13**

1704.04163 | cs.DS

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

**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

**2017-12-20**

1712.07509 | cs.IT

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

**2017-10-30**

1710.11253 | cs.DS

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