# A PTAS for $\ell_{0}$-Low Rank Approximation:
Solving Dense CSPs over Reals

Vincent Cohen-Addad Google Research, France Chenglin Fan Sorbonne Université,
France Suprovat Ghoshal Northwestern University, USA Euiwoong Lee University
of Michigan, USA Arnaud de Mesmay LIGM, CNRS, Univ. Gustave Eiffel, ESIEE
Paris, F-77454 Marne-la-Vallée, France Alantha Newman Laboratoire G-SCOP
(CNRS, Grenoble-INP), France Tony Chang Wang University of Wisconsin-Madison,
USA

###### Abstract

We consider the $\ell_{0}$-Low Rank Approximation problem, where the input
consists of a matrix $A\in\mathbb{R}^{n_{R}\times n_{C}}$ and an integer $k$,
and the goal is to find a matrix $B$ of rank at most $k$ that minimizes
$\|A-B\|_{0}$, which is the number of entries where $A$ and $B$ differ. For
any constant $k$ and $\varepsilon>0$, we present a polynomial time
$(1+\varepsilon)$-approximation time for this problem, which significantly
improves the previous best $\mathrm{poly}(k)$-approximation.

Our algorithm is obtained by viewing the problem as a Constraint Satisfaction
Problem (CSP) where each row and column becomes a variable that can have a
value from $\mathbb{R}^{k}$. In this view, we have a constraint between each
row and column, which results in a dense CSP, a well-studied topic in
approximation algorithms. While most of previous algorithms focus on finite-
size (or constant-size) domains and involve an exhaustive enumeration over the
entire domain, we present a new framework that bypasses such an enumeration in
$\mathbb{R}^{k}$. We also use tools from the rich literature of Low Rank
Approximation in different objectives (e.g., $\ell_{p}$ with $p\in(0,\infty)$)
or domains (e.g., finite fields/generalized Boolean). We believe that our
techniques might be useful to study other real-valued CSPs and matrix
optimization problems.

On the hardness side, when $k$ is part of the input, we prove that
$\ell_{0}$-Low Rank Approximation is NP-hard to approximate within a factor of
$\Omega(\log n)$. This is the first superconstant NP-hardness of approximation
for any $p\in[0,\infty]$ that does not rely on stronger conjectures (e.g., the
Small Set Expansion Hypothesis).

##  1 Introduction

Computing a low rank approximation of a given matrix is one of the most
fundamental algorithmic tasks in data analysis and machine learning. Formally,
given a matrix $A\in\mathbb{R}^{n_{R}\times n_{C}}$ and an integer
$k\in{\mathbb{N}}$, the goal is to compute a matrix
$B\in\mathbb{R}^{n_{R}\times n_{C}}$ of rank at most $k$ that minimizes some
distance measure between $A$ and $B$. The Frobenius norm
$\|A-B\|_{F}=(\sum_{i,j}(A_{i,j}-B_{i,j})^{2})^{1/2}$ and its generalizations
to Schatten norms can be optimized in polynomial time for any $k$, and there
is a rich literature on faster algorithms to compute them, possibly for
special classes of matrices or more restricted models of computations [CW17a,
CW17b, MW17, JLS+21, BCW20, LW20, WY22, BCW22]. Many variants that are not
expected to have a polynomial time exact algorithm have been actively studied
as well, including tensor versions [SWZ19] or weighted versions [RSW16, BWZ19]
where each entry has different weights. The (entrywise) $\ell_{p}$ objective
$\|A-B\|_{p}:=(\sum_{i,j}(A_{i,j}-B_{i,j})^{p})^{1/p}$ is another
generalization of the Frobenius norm [CGK+17, SWZ17, BBB+19, MW21]. This
objective with $0\leq p<2$ is generally considered to be more robust than the
Frobenius norm, because in the Frobenius norm, a few outlier entries (whose
values are very far from correct) can have a large effect on the other entries
in a solution.

In this paper, we focus on $\ell_{0}$-Low Rank Approximation ($\ell_{0}$-LRA),
where $\|A-B\|_{0}$ is defined to be the number of entries where $A$ and $B$
differ. It is a maximally robust objective function in the aforementioned
sense, which was used in the notion of robust PCA [CLMW11]. The choice of the
$\ell_{0}$ metric also makes particular sense in contexts where the data is
not endowed with a natural underlying metric. The $\ell_{0}$-LRA problem
coincides with the matrix rigidity problem over the reals, which has been
studied in the context of complexity theory [Gri76, Val77] and parameterized
complexity [FLM+17], and is closely related to matrix completion [Joh90, CP10,
KMO10, Rec11]. The special case when $A\in\\{0,1\\}^{m\times n}$, which is NP-
hard even for $k=1$ [GV18, DHJ+18], has been also well studied [FGL+19,
FGP20]. Another related problem is the Metric Violation Distance (MVD) problem
where the input is a symmetric matrix $A\in\mathbb{R}^{n\times n}$ and the
goal is to find a matrix $B\in\mathbb{R}^{n\times n}$ representing the
pairwise distances in a metric space to minimize $\|A-B\|_{0}$ [FRVB18,
CFLM22].

The previous best approximation algorithms for $\ell_{0}$-LRA, given by
Bringmann, Kolev, and Woodruff [BKW17], achieve an $O(k^{2})$-approximation in
time $n^{O(k)}$ and an $(2+\varepsilon)$-approximation when $k=1$. (Let
$n:=\max(n_{R},n_{C})$.) It is in stark contract to
$(1+\varepsilon)$-approximations for fixed $k$ when $p\in(0,2)$ or the domain
is constant-size [BBB+19, FGL+19]. We bridge this gap, showing that
$\ell_{0}$-LRA admits a PTAS for every constant $k$ as well.

######  Theorem 1.1.

For any fixed constants $k\in{\mathbb{N}}$ and $\varepsilon>0$, there exists a
$(1+\varepsilon)$-approximation algorithm for $\ell_{0}$-Low Rank
Approximation that runs in time
$n^{2^{\mathrm{poly}(k/\varepsilon)}}\mathrm{poly}(\tau)$, where $\tau$ is an
upper bound on the bitsize of the coefficients of the input matrix.

Our algorithm works by computing matrices $U\in\mathbb{R}^{n_{R}\times k}$ and
$W\in\mathbb{R}^{n_{C}\times k}$ so that $B=UW^{T}$. Each entry of our
solution $U$, $W$ and $B$ is not guaranteed to be a rational number and will
be described by the Thom encoding; roughly, it will be the unique solution to
a system of an $2^{\mathrm{poly}(k/\varepsilon)}$ polynomial (in)equalities
whose coefficients have bit complexity at most $\mathrm{poly}(\tau)$. See
Section 2 for more background.

Our result is inspired by the connection between Low Rank Approximation and
the well-studied topic of dense Constraint Satisfaction Problems (CSPs). In
the context of $\ell_{0}$-LRA, we consider each row and column as a variable
that can have a value from $\mathbb{R}^{k}$. For each row $i$ and column $j$,
we have a constraint that is satisfied if $\langle
u_{i},v_{j}\rangle=A_{i,j}$, where $u_{i}$ and $v_{j}$ denote the vectors
chosen by $i$ and $j$ respectively. Dense CSPs are a central topic in
approximation algorithms, and there are PTASes using various methods (e.g.,
sampling [AKK95, ADLVKK03, dlVKKV05, MS08, KS09, BHHS11, Yar14, MM15],
regularity lemma [FK96, COCF10], convex hierarchies [dlVKM07, BRS11, GS11,
YZ14]).

However, all previous techniques crucially rely on the fact that the domain of
a CSP is finite (and bounded as a function of $n$), which makes it nontrivial
to apply these ideas to $\ell_{0}$-LRA. We overcome such a difficulty by
introducing a new framework that allows us to use tools from both the Low Rank
Approximation and dense CSP literatures (see Section 1.1 for more detailed
description of our techniques). We hope that it might be useful for other
matrix problems and CSPs with real domains. On our way to proving Theorem 1.1,
our first result is to provide an $\varepsilon$-_additive_ approximation
algorithm, which returns a solution $B$ with the guarantee that $\|A-B\|_{0}$
is at most the optimal value plus $\varepsilon n_{R}n_{C}$.

######  Theorem 1.2.

For any fixed constants $k\in{\mathbb{N}}$ and $\varepsilon>0$, there exists
an algorithm computing an $\varepsilon$-additive approximation to
$\ell_{0}$-LRA that runs in time
$n^{(1/\varepsilon)^{\mathrm{poly}(k)}}\mathrm{poly}(\tau)$, where $\tau$ is
an upper bound on the bitsize of the coefficients of the input matrix.

On the hardness side, when $k$ is part of the input, we prove that
$\ell_{0}$-Low Rank Approximation is NP-hard to approximate within a factor of
$\Omega(\log n)$, which implies that the superpolynomial dependence on $k$ is
necessary. To the best of our knowledge, this is the first superconstant NP-
hardness of approximation for any $p\in[0,\infty]$ that does not rely on
stronger conjectures. The only known $\omega(1)$-hardness of $\ell_{p}$-Low
Rank Approximation, which holds for $p\in(1,2)$, relies on the Small Set
Expansion Hypothesis [BBB+19].

######  Theorem 1.3.

When $k$ is part of the input, it is NP-hard to approximate $\ell_{0}$-Low
Rank Approximation within a factor of $\Omega(\log n)$.

Theorem 1.1 features a doubly-exponential dependency on the parameters $k$ and
$\varepsilon$, and this dependency is not fixed-parameter tractable.
Furthermore, our algorithm heavily relies on algorithms from real algebraic
geometry that quickly become impractical. Whether one can improve this
complexity, both from a theoretical and practical point of view, is the main
question arising from our work. It would also be interesting to adapt our
framework to other problems which can be phrased as CSPs over the reals, such
as other matrix factorization problems, or finite-dimensional versions of
problems involving distances (see, e.g., [FRVB18, CFLM22]).

###  1.1 Techniques

In this section, we give an overview of the techniques involved in the proof
of Theorems 1.1 and 1.2. Let $A\in\mathbb{R}^{n_{R}\times n_{C}}$ be the input
matrix, let $UW^{T}$ be an optimal solution where $U\in\mathbb{R}^{n_{R}\times
k}$ and $W\in\mathbb{R}^{n_{C}\times k}$. We denote by $u_{i}$ the $i$th row
of $U$ and $w_{i}$ the $i$th row of $W$ (as column vectors). Let
$OPT=|\\{(i,j):A_{i,j}\neq\langle u_{i},w_{j}\rangle\\}|$ be the number of
errors that the optimal solution makes.

Both algorithms rely on PTASes for constraint satisfaction problems, which we
first introduce. A Constraint Satisfaction Problem of arity $2$ (2-CSP)
consists of (i) a family of $n$ variables $V$, which can take values within a
given alphabet $D$ (also called domain), and (ii) a family of constraints $C$
between some pairs of variables, where each constraint is a subset of $D\times
D$. An assignment is a map $\varphi:V\rightarrow D$. The set of pairs of
variables between which there is a constraint is encoded in a graph $G$,
called the primal graph (or Gaifman graph) of the 2-CSP. The goal is to find
an assignment that maximizes the number of satisfied constraints (Max-2-CSP),
or that minimizes the number of unsatisfied constraints (Min-2-CSP). While
these two problems are obviously equivalent in the realm of exact algorithms,
providing approximation algorithms leads to different challenges in the
minimization and the maximization setting. In a nutshell, efficiently
approximating a Min-2-CSP requires performing very well on the instances where
almost all the constraints are satisfiable, while approximating a Max-2-CSP
requires performing well in the opposite regime, when a very small number of
constraints is satisfiable. This explains why when the graph is dense and the
alphabet size is of constant size, it is much easier to obtain a PTAS for the
Max-CSP: in this regime, the maximum number of satisfiable constraints is
$\Omega(n^{2})$, as can easily be proved by taking a random assignment.
Therefore, in order to design a PTAS for a dense Max-2-CSP and a constant-size
alphabet, it suffices to devise a $\varepsilon$-additive approximation, akin
to the one we are aiming for in Theorem 1.2.

Our approach to prove Theorems 1.1 and 1.2 is to formulate the $\ell_{0}$-Low
Rank Approximation problem as 2-CSP, where the primal graph is the complete
bipartite graph. There is one variable for each row and each column, the
alphabet is $\mathbb{R}^{k}$ and the constraint between the row $i$ and the
column $j$ is $\langle u_{i},w_{j}\rangle=A_{i,j}$. Then we would like to use
the PTASes for such dense CSPs available in the literature, but the key issue
is that our alphabet size is infinite. Therefore, the most technical part in
both our algorithms consists in reducing the alphabet size to a constant size:
computing for each row $i$ and column $j$ a constant-size alphabet
$\Sigma_{i}$ or $\Sigma_{j}$ of vectors in $\mathbb{R}^{k}$, such that there
exists a near-optimal solution using exclusively vectors from these alphabets.
Throughout this overview, whenever we refer to “constant”, the constant
depends on $k$ and $\varepsilon$; we refer to the proofs for the precise
values.

####  1.1.1 Additive approximation scheme: Theorem 1.2

A classical approach to design additive approximation schemes for dense CSPs
is to sample a constant number of variables [MS08, Yar14], guess their values
and then extrapolate from this sample the values of all the other variables.
Since our domain size is infinite, we cannot guess the values here, and
instead our key contribution is to prove the existence of a constant-size set
of variables and constraints among them beyond the ones given by matrix
entries such that _any_ solution to the constraints between those can be
extended to be a near-optimal solution on the full set of variables. Such a
solution can be computed using real algebraic solvers [BPR10]. This idea might
be of independent interest to other constraint satisfaction problems over the
reals.

We now get into more details. The entire algorithm behind Theorem 1.2 is
outlined in Figure LABEL:A:mainalgo. For simplicity, we assume in this section
that $n:=n_{R}=n_{C}$.

##### The rigid case.

We first explain the intuition behind it by investigating a particular case.
We first assume that there exists an optimal solution $U,W$ that is _rigid_ :
every $k\times k$ submatrix of $U$ and $W$ has full rank (recall that $k$ is
the target rank in our $\ell_{0}$-Low Rank Approximation problem). If at most
$\varepsilon n^{2}$ constraints are satisfied, any solution is an
$\varepsilon$-additive approximation. Otherwise, we consider the bipartite
graph $G$, where the vertices are the rows and columns of $A$, and there is an
edge whenever the constraint between row $i$ and column $j$ is satisfied,
i.e., $\langle u_{i},w_{j}\rangle=A_{i,j}$. Since this graph has at least
$\varepsilon n^{2}$ edges, the Kovari-Sòs-Turan theorem [KST54] guarantees
that it admits a complete bipartite subgraph $G^{\prime}:=K_{k,k}$ as a
subgraph. This complete bipartite subgraph enforces a solution on the
corresponding rows of $U$ and columns of $W$, which is unique up to the
natural symmetries of the problem. More formally, by our rigidness assumption,
up to111This does not change the value of the solution since one can change
$W$ accordingly: $(UC)(C^{-1}W^{T})=UW^{T}$. applying an invertible matrix $C$
to $U$ we can assume that the submatrix of $U$ induced by the rows of
$G^{\prime}$ is the identity, and then $W$ must exactly match the submatrix of
$A$ induced by $G^{\prime}$. Then, every row $u_{i}$ that is adjacent in $G$
to all the columns of $G^{\prime}$ (thus forming a $K_{k+1,k}$) also has its
value completely determined by the constraints of $G^{\prime}$, since it is
the unique solution to a linear system of full rank.

The Kovari-Sòs-Turan theorem can be strengthened to a supersaturated version,
showing that (Lemmas 2.2 and 3.2) not only there exists a $K_{k+1,k+1}$
subgraph, but there are a lot of them, and actually most edges of $G$ belong
to many of them. This suggests the following algorithm. First, we sample a
constant number of columns and vertices uniformly at random, and we guess the
subgraph $G^{\prime}$ of $G$ induced by this subset, which we call the _core_
of the solution. Now, let us assume that we can compute a family of rows and
columns for this constant-size core that exactly matches the optimal solution
(perhaps modulo the natural symmetries of the problem). Then, for any edge
$(i,j)$ not in $G^{\prime}$ (except for a negligible portion of those), we can
prove that it belongs in $G$ to a $K_{k+1,k+1}$, where the other $2k$ vertices
are in $G^{\prime}$. Therefore, by the rigidness assumption, the rows and
columns of $G^{\prime}$ induce a unique solution for $i$ and $j$, which thus
matches the optimal solution. We can thus define for a vertex $v$ an alphabet
$\Sigma_{v}$ as being, for each possible choice of $K_{k,k}$ in $G^{\prime}$
that $v$ could be adjacent to, the unique solution that it induces for $v$.
Since this alphabet has constant size for each vertex, we can now appeal to
standard Max-2-CSPs algorithms [Yar14] to obtain the required
$\varepsilon$-additive approximation.

This algorithm requires us to compute the restriction of an optimal solution
to the constant-size subset of rows and columns induced by $G^{\prime}$. Such
a solution must satisfy a family of quadratic equations: for all $(i,j)\in
G^{\prime}$, we should have $\langle u_{i},v_{j}\rangle=A_{i,j}$, where
$u_{i}$ and $v_{j}$ are unknown vectors in $\mathbb{R}^{k}$. We can solve such
systems of equations using algorithms from real algebraic geometry, which more
generally can be used to solve222There are subtle issues involving what it
means to “solve” such a system of equations, see the discussion in Section 2.
any polynomial system of (in)-equations (or even any problem in the
Existential Theory of the Reals, see Section 2) in exponential time. Such
algebraic solvers have already been used in multiple algorithms in Low Rank
Approximation and its variants, see for example [FGP20, RSW16, SWZ19], but one
key difference is that in [RSW16, SWZ19], they were used to optimize the
objective function (which was itself polynomial) over a sketch. This is not
possible for us because we use the $\ell_{0}$-norm. Since in our case, the
systems have constant size, we can afford to pay the exponential complexity.
However, a key issue appears: in contrast to the case where the entire
$G^{\prime}$ was equal to $K_{k,k}$, in general $G^{\prime}$ can be an
arbitrary graph so that such a solution will in general not be unique, even
after quotienting by the natural symmetries of the problem. Therefore, it
could be that the solution that we compute on $G^{\prime}$ is fundamentally
different from the optimal one, thus leading to alphabets which do not contain
an optimal solution.

${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}u_{5,1}}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}u_{5,2}}$
$\left[\vbox{\hrule
height=47.90767pt,depth=47.90767pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=47.90767pt,depth=47.90767pt,width=0.0pt}\right]$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
x x
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
x x x x
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
x x
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}3}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
$\left[\vbox{\hrule
height=47.90767pt,depth=47.90767pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=47.90767pt,depth=47.90767pt,width=0.0pt}\right]$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
$\left[\vbox{\hrule
height=21.16287pt,depth=21.16287pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=21.16287pt,depth=21.16287pt,width=0.0pt}\right]$$U$$W^{T}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
$\left[\vbox{\hrule
height=47.90767pt,depth=47.90767pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=47.90767pt,depth=47.90767pt,width=0.0pt}\right]$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
x x
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
x x x x
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
x x
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}3}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
$\left[\vbox{\hrule
height=47.90767pt,depth=47.90767pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=47.90767pt,depth=47.90767pt,width=0.0pt}\right]$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1}$
${\definecolor[named]{.}{rgb}{0,0,0}\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}0}$
$\left[\vbox{\hrule
height=21.16287pt,depth=21.16287pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=21.16287pt,depth=21.16287pt,width=0.0pt}\right]$$U$$W^{T}$

Figure 1: Adding rows to the core in order to control its inner dependencies.
The x values are not in the graph $G$ of the optimal solution. Left: Choosing
arbitrary solutions for the yellow and the green $K_{2,2}$’s might lead to an
unsolvable system of equations for the fifth row (blue). Right: Adding the
fifth row to the core synchronizes the yellow and green $K_{2,2}$’s.

We solve this issue by adding additional data in a non-random way to the core
$G^{\prime}$. We explain the main idea on a simple instance, which is
illustrated in Figure 1 with $k=2$. Suppose that $G^{\prime}$ consists of two
vertex-disjoint $K_{k,k}$ subgraphs of $G$. Solving the corresponding system
of equations and taking an arbitrary solution would lead to vectors for rows
and columns which are completely uncorrelated between the two subgraphs. If
some row $i$ not in $G^{\prime}$ is adjacent in $G$ to all the columns of
$G^{\prime}$, the values of the row $i$ suggested by the two subgraphs will
therefore never match. In such a case, we add the row $i$ to the core,
yielding a _supercore_. When we solve the system of polynomial equations on
this supercore, the added row will have the effect of correlating the
solutions on the two subgraphs of $G^{\prime}$. Of course, we should not add
all such rows to the core, since we want the supercore to also be constant-
size, but our framework shows that it suffices to add a constant number of
such rows and columns in order to account for all the required correlations
between the various parts of the core in the optimal solution. We emphasize
that the rows and columns added in the supercore cannot in general be chosen
randomly. Thus our algorithm does not actually proceed by sampling and
requires enumerating all the subsets up to some constant size: this is the
reason for the $n^{f(k,\varepsilon)}$ complexity of our algorithm in Theorem
1.2, as opposed to the FPT complexity of most PTASes in the literature for
dense Max-CSPs.

##### Extending to the general case.

In the general case, we cannot assume that there is an optimal solution that
is rigid. In that setting, our algorithm still starts by guessing a supercore
$G^{\prime}$ and solving the corresponding system of polynomial equations.
However, such a supercore will not in general induce a unique solution for a
row or a column not contained in it, even if it is fully adjacent to a
$K_{k,k}$ in $G^{\prime}$, since the corresponding linear system of equations
may not be full rank: this poses an issue when defining the alphabets. If one
takes an arbitrary solution, then for a row $i$ and a column $j$ that are not
in the supercore but form an edge $(i,j)$ in $G$, even if one guesses
correctly to which $K_{k,k}$’s $i$ and $j$ are attached in $G$, the vectors
$u_{i}$ and $w_{j}$ will in general not come from an optimal solution. Thus
there is no guarantee that the constraint $(i,j)$ will be satisfied.

We solve this issue by adding even more data to the supercore. Since it has
constant-size, we can afford to guess the entire system of linear dependencies
between its elements, as this is encoded in a combinatorial object called a
matroid [Oxl06]. Then, for vertices not in the supercore, we include in the
alphabet not only to which parts of the core they are attached, but also with
which of the independent sets of this matroid they are dependent in the
optimal solution. This information is encompassed in submatrices that we call
_pieces_ , which are also constantly many. Then we prove that guessing
correctly the information of which edge belongs to which pieces will suffice
to ensure correct edges, even outside of the supercore; this follows from an
easy linear algebraic Lemma 3.3.

We emphasize that due to the infinite size of the alphabet, our additive
approximation scheme in Theorem 1.2 does not readily provide a PTAS for the
maximization version of $\ell_{0}$-Low Rank Approximation, since there is in
general no $\Omega(n^{2})$ lower bound for the value of this CSP despite the
density of the primal graph. We leave the existence of such a PTAS as an open
question.

####  1.1.2 Multiplicative approximation scheme: Theorem 1.1

Based on the additive approximation scheme, we introduce high-level ideas
between our multiplicative approximation scheme for Theorem 1.1. Like the
additive approximation scheme, our algorithm also works by reducing the
alphabet size to a constant. In order to do so, our new framework here
partitions the set of entries $[n_{R}]\times[n_{C}]$ into rectangular blocks
(there are at most $k\times k$ of them) and handle them separately in the
following natural ways: if a block $B$ has

  * •

$|B|\gg OPT$ (called clean): Techniques for constant-size alphabets almost
suffice, as random entries from $B$ are correct in the optimal solution and
reveal useful information about it.

  * •

$|B|\ll OPT$ (called dirty): We can ignore $B$ as it will not contribute much
to the objective.

  * •

$|B|\approx OPT$ (called half-clean): Use the additive PTAS, because an
additive approximation is also a multiplicative approximation in this case.

One technical and conceptual challenge is that the algorithm will never be
able to learn where the blocks are, but our algorithm still manages to handle
them using careful definitions of the blocks (only in the analysis) and the
additional features of the additive PTAS. We shall explain the ideas in more
detail below.

##### Basic strategy.

Recall that given an instance of $\ell_{0}$-Low Rank Approximation
$A\in\mathbb{R}^{n_{R}\times n_{C}}$ with an optimal solution $UW^{T}$, we
view this as a CSP where there is a variable for each row and column, and the
goal is to choose a value $u_{i}$ from the alphabet $\Sigma=\mathbb{R}^{k}$
for each row $i$ and $w_{j}\in\Sigma$ for each column $j$ to satisfy the
constraints given by $A$. It is natural to review previous approaches for
dense Min-CSPs [KS09, MMMN23] and Low Rank Approximation on Finite Domains
[BBB+19]. With an oversimplification that ignores important technical details,
their main ideas, when the alphabet set is general $\Sigma$, can be roughly
summarized as:

  1. 1.

Sample a constant number of column indices $s_{1},\dots,s_{t}\in[n_{C}]$.

  2. 2.

Guess the value of each $s_{i}$ in the optimal solution; i.e., guess
$w_{s_{i}}\in\Sigma$.

  3. 3.

Based on $w_{s_{1}},\dots,w_{s_{t}}$, greedily choose $u_{p}$ for each
$p\in[n_{R}]$; i.e., choose $u_{p}$ that makes the least number of errors with
$w_{s_{1}},\dots,w_{s_{t}}$.

  4. 4.

Given the value of every $u_{p}$, greedily choose $w_{q}$ for every
$q\in[n_{C}]$.

Having $\Sigma=\mathbb{R}^{k}$ presents a challenge in almost every step. For
us, the biggest challenge is Step 2, where we cannot guess the values of the
sampled columns in the optimal solution via exhaustive enumeration. Therefore,
our overall goal is to reduce the alphabet set from $\mathbb{R}^{k}$ to
constant-size sets; formally, our algorithm will construct the alphabet set
$\Sigma_{p}$ for each row and column $p$ with $|\Sigma_{p}|\leq
O_{k,\varepsilon}(1)$ so that there exists a near-optimal solution where each
row and column draws a value from their given alphabet sets. (Actually, the
algorithm creates polynomially many such instances with the guarantee that one
of them contains a near-optimal solution using their alphabets.)

Another smaller challenge related to Step 3 is that even given the correct
values for $w_{s_{1}},\dots,w_{s_{t}}$, possibly none of $u_{i}$’s can be
determined. For example, if most of the rows and columns belong to a proper
subspace $T\subsetneq\mathbb{R}^{k}$ and all $w_{s_{1}},\dots,w_{s_{t}}$ are
in $T$, then at best the algorithm can determine $u_{p}$’s projection to $T$,
but not its exact position in $\mathbb{R}^{k}$ (while most of the errors made
by the optimal solution might come from the few $u_{p}$’s and $w_{q}$’s
outside $T$). Inspired by the previous approaches, we handle this issue by
dividing $\mathbb{R}^{k}$ (and the set of rows and columns) into layers and
obtain uniform samples from each layer. The algorithm will not know the
layers, so sampling for the rest of the subsection is just needed to show the
existence of a good seed set. The algorithm will enumerate all possible seed
sets of certain size.

Our column layers are sets $J_{1},\dots,J_{\ell_{C}}$ with $\ell_{C}\leq k$
that partition $[n_{C}]$ with associated subspaces $\emptyset=T_{J,0}\subseteq
T_{J,1}\subseteq\dots\subseteq T_{J,{\ell_{C}}}=\mathbb{R}^{k}$ such that for
any $j\in[\ell_{C}]$, $\\{w_{q}:q\in J_{j}\\}\subseteq T_{J,j}$. We require
that the layer sizes are decreasing quickly (e.g.,
$|J_{j}|\leq\alpha|J_{j-1}|$) and crucially, each layer is full; for any
$j\in[\ell_{C}]$, no subspace $T^{\prime}$ with $T_{J,{j-1}}\subseteq
T^{\prime}\subsetneq T_{J,j}$ contains more than a $(1-\beta)$ fraction of
$J_{j}$ with some constants $\alpha,\beta\in(0,1)$. Even though in the actual
algorithm they are both set to be constants depending only on $k$, for
simplicity of this overview, let us make the key simplifying assumption that
$\alpha=o_{n}(1)$ while $\beta$ is still a constant. (This will avoid the
notion of superlayers and hyperlayers in Section 4.)

Once we obtain samples $\\{s_{j,1},\dots,s_{j,t}\\}$ from each layer $J_{j}$
and guess their values $\\{w_{s_{j,q}}\\}_{q\in[t]}$ in a near-optimal
solution, one can show that the standard algorithm, choosing greedily $u_{p}$
for every $p\in[n_{R}]$ and choosing greedily $w_{q}$ for every $q\in[n_{C}]$
guarantees a good solution. (See Phase 4 of Section 4 for details.) Therefore,
once the the alphabet size for columns becomes a constant, the algorithm can
obtain samples, guess the values of the samples, and perform the greedy
decisions to obtain a PTAS.

Now we describe our main alphabet-reduction algorithm to construct a constant-
size alphabet set for each row and column. Note that in the beginning, the
algorithm has no information about the initial optimal solution $U$ and $W$.
While describing the algorithm, we will also transform $U$ and $W$ such that
(1) the transformed solution is still near-optimal, and (2) the algorithm
acquires more information about them as it proceeds. Just like Section 4, we
present this algorithm in three phases.

##### Phase 1: Obtaining initial samples.

Our alphabet-reduction algorithm also begins with sampling. As well as the
column layers, construct the row layers $I_{1},\dots,I_{\ell_{R}}$ with the
subspaces $T_{I,1},\dots,T_{I,\ell_{R}}$ for some $\ell_{R}\leq k$. Call
$B_{i,j}:=I_{i}\times J_{j}$ the $(i,j)$th block. Then we have
$\ell_{R}\times\ell_{C}$ blocks. By guessing, we can assume that the algorithm
knows all block sizes and $OPT$, the number of errors that the optimal
solution makes. (There are $n^{O(k)}$ possibilities).

Then we compare the size of each block $|B_{i,j}|$ to $OPT$. If $|B_{i,j}|\ll
OPT$, we call it dirty; we can afford to make errors in the entire block, so
we can safely ignore it. Otherwise, if $|B_{i,j}|\gg OPT$, we call it clean;
we can get a lot of information of this block by samples, because when we
uniformly sample rows from $I_{i}$ and columns from $J_{j}$, most of the
entries between them are correct; the entries of the input matrix $A$ are the
correct inner product values between optimal vectors. We call all other blocks
half-clean. As these definitions only depend on the sizes of the blocks, we
have a natural monotonicity property: for instance, if $B_{i,j}$ is clean then
$B_{i-1,j}$ is as well, and if $B_{i,j}$ is dirty, $B_{i+1,j}$ is dirty too.
Another crucial consequence of this definition (and our key simplifying
assumption) is that each row and column belongs to at most one half-clean
block. This will be important when the algorithm applies the additive PTAS in
Phase 3. See Figure 2 for an example.

Figure 2: There are $16\times 16$ blocks. Empty cells are clean, half-shaded
cells are half-clean, and full-shaded cells are dirty.

The algorithm obtains samples from each row and column layer; call them
$\\{r_{i,p}\\}_{i\in[\ell_{R}],p\in[t]}$ and
$\\{s_{j,q}\\}_{j\in[\ell_{C}],q\in[t]}$ for some constant $t$. Since each
$T_{I,i}$ is full, the row samples will contain a basis of $\mathbb{R}^{k}$,
so by applying an appropriate transformation $U\leftarrow UC,W\leftarrow
W(C^{-1})^{T}$ for some invertible $C\in\mathbb{R}^{k\times k}$ (only in the
analysis), the algorithm knows $T_{I,i}$ for every $i\in[\ell_{R}]$. For a
clean block $B_{i,j}$, using the correct entries between the sampled rows and
columns, the algorithm can even recover $T_{i,j}$, which is the projection of
$T_{C,j}$ to $T_{I,i}$ and losslessly captures the interaction between the
vectors in $B_{i,j}$.

##### Phase 2: Handling clean blocks.

One (non-)feature of our alphabet-reduction algorithm is that it will never
determine whether a particular row or column belongs to a certain layer.
Instead, for each row-layer pair $(p,i)\in[n_{R}]\times[\ell_{R}]$, the
algorithm will construct a set of vectors $\Sigma_{p,i}$ that contains the
correct vector $u_{p}$ if $p$ indeed belongs to $I_{i}$ in the current near-
optimal solution $(U,W)$. In this phase, we begin this process from clean
blocks, where each $(p,i)$ pair chooses only one vector $u_{p,i}$ inside
$T_{i,m(i)}$ instead of $\mathbb{R}^{k}$, where $m(i)\in[\ell_{C}]$ is the
largest index $j$ where $B_{i,j}$ is clean. In particular, when $p\in I_{i}$
in the current near-optimal solution, $u_{p,i}$ is exactly the projection of
$u_{p}$ to $T_{i,m(i)}$, denoted by $u_{p}|_{T_{i,m(i)}}$.

More concretely, for each row $p\in[n_{R}]$ and $i\in[\ell_{R}]$, we let the
column samples $\\{s_{j,q}\\}_{j\in[m(i)],q\in[t]}$ vote for the projection of
$u_{p}$ to $T_{i,m(i)}$ and call the winner $u_{p,i}$. Formally,

$u_{p,i}=\mathrm{argmin}_{u\in
T_{i,m(i)}}\sum_{j=1}^{m(i)}|\\{q\in[t]:A_{p,s_{j,q}}\neq\langle
u,w_{s_{j,q}}|_{T_{i,j}}\rangle\\}|\cdot(|J_{j}|/t)$

where ties are broken arbitrarily. The goal is to ensure that
$u_{p,i}=u_{p}|_{T_{i,m(i)}}$ if $p\in I_{i}$. Of course, this cannot happen
always, but we will conduct the following transformation that forces it.

  * •

For every $p\in[n_{R}]$, let $i\in[\ell_{R}]$ such that $p\in I_{i}$.

    * –

If $u_{p,i}$ is indeed the projection of $u_{p}$ to $T_{i,m(i)}$, then do not
change anything.

    * –

Otherwise, say $p$ is mistaken and let $u_{p}\leftarrow u_{p,i}$. By doing
this, we (conservatively) make every entry $A_{p,q}$ with $q\in J_{j}$ and
$j>m(i)$ incorrect.

Our main technical lemma (Lemma 4.2) shows that this transformation of $U$
ensures that the solution pair $(U,W)$ is still near-optimal. In particular,
it shows that (1) the chosen $u_{p,i}$ will be again nearly optimal in the
clean blocks $B_{i,1},\dots,B_{i,m(i)}$, and (2) the probability that $p$ is
mistaken is small so that the additional error in half-clean or dirty blocks
due to a mistake will be small in expectation. We do the almost same for
columns to compute column vectors $w_{q,j}\in T_{m(j),j}$ for each
$q\in[n_{C}]$ and $j\in[\ell_{C}]$.

##### Phase 3: Handling half-clean blocks.

Finally, the algorithm constructs the alphabet set that will contain a good
solution for half-clean blocks as well. For one row-layer pair $(p,i)$, we
construct the set of vectors $\Sigma_{p,i}$ such that (1) for any
$u\in\Sigma_{p,i}$, the projection of $u$ to $T_{i,m(i)}$ is equal to
$u_{p,i}$ constructed in the previous phase, and (2) if $p$ indeed belongs to
$I_{i}$ in the current near-optimal solution, then $\Sigma_{p,i}$ contains
$u_{p}$, the correct vector of $p$ in the current near-optimal solution.

The main idea here is to apply the additive PTAS to every half-clean block
$B_{i,j}$. By definition, $|B_{i,j}|=\Theta(OPT)$, so an additive
$\varepsilon$-approximation in $B_{i,j}$ will lead to an overall
multiplicative approximation. But the crucial bottleneck is that we will never
know where $B_{i,j}$ is! As previously mentioned, our alphabet-reduction
algorithm will never determine $p\in I_{i}$ for any $p\in[n_{R}]$ and
$i\in[\ell_{R}]$. What we do know is $u_{p,i}$, which is the correct
projection of $p$’s near-optimal vector $u_{p}$ to $T_{i,j}$, if $p$ indeed
belongs to $I_{i}$.

We resolve this issue by, for every half-clean block $B_{i,j}$, running the
additive PTAS algorithm for the entire matrix $A$ pretending that every row
belongs to $I_{i}$ and every column belongs to $J_{j}$. Though there are
exponentially many candidates for $B_{i,j}$ inside $A$, the structure of our
additive PTAS guarantees that any submatrix of $A$ corresponding to a block
$I^{\prime}\times J^{\prime}$ with
$I^{\prime}\subseteq[n_{R}],J^{\prime}\subseteq[n_{C}]$ will admit a constant-
size subset of $I^{+}\subseteq I^{\prime}$ and $J^{+}\subseteq J^{\prime}$
that suggest a set of vectors for everyone in $I\cup J$ containing their
correct vectors in the near-optimal solution. Then, even without knowing
actual $I_{i}$ and $J_{j}$, the algorithm can try all constant-size subsets
$I^{+}$ and $J^{+}$ that suggest a constant-size alphabet for every
$p\in[n_{R}]$ and $q\in[n_{C}]$! Of course, if $i\notin I_{i}$, then this
suggestion does not have any guarantee, but we do know that if $i\in I_{i}$,
this suggestion will contain the correct vector. Also note that this strategy
depends on the fact that each row or column belongs to at most one half-clean
block; otherwise, one row would have received more than one “correct
suggestions” where each correct suggestion yields a good solution for only one
half-clean block.

Therefore, we run the additive PTAS for each half-clean hyperblock, and for
each choice of $(I^{+},J^{+})$’s, we have an instance of $\ell_{0}$-LRA where
each row or column $p$ gets a constant-size alphabet set
$\Sigma_{p}=\cup_{i}\Sigma_{p,i}$, with the guarantee that, for at least one
choice of $(I^{+},J^{+})$’s, there exists a near-optimal solution where every
row and column chooses a vector from the given alphabet set. The alphabet-
reduction algorithm is completed, so the standard finite-domain-CSP algorithm
(sample columns, exhaustively guess the values of the sampled columns,
greedily decide the value of each row based on the sampled columns, and
greedily decide the value of each column based on all the rows) will result in
a PTAS.

##  2 Preliminaries

##### Algorithms for real semialgebraic sets.

Our algorithm for Theorem 1.2 makes heavy use of algorithms of real algebraic
geometry to solve systems of polynomial equations over the reals, which we use
as a black-box. We refer to the book of Basu, Pollack and Roy [BPR10] for all
the necessary background on this topic and highlight here the precise results
that we rely on. A _semialgebraic set_ is the set of solutions to a system of
polynomial equations or inequations over the reals, or any finite union of
such sets. The _projection_ of a semialgebraic set
$X\subseteq\mathbb{R}^{n_{1}+n_{2}}$ on a linear subspace $\mathbb{R}^{n_{1}}$
is the set $\\{x_{1},\ldots,x_{n_{1}}\mid\exists
x_{n_{1}+1},\ldots,x_{n_{2}}\textrm{ such that }x_{1},\ldots,x_{n_{2}}\in
X\\}$. A consequence of the Tarski-Seidenberg theorem (see, e.g., [BPR10,
Theorem 2.77]) is that a projection of a semi-algebraic set is another
semialgebraic set, for which the equations can be computed. An algorithmic
reformulation that we will extensively rely on is as follows. The _Existential
Theory of the Reals_ is the following decision problem: we are given a formula
of the form $\exists x_{1},\ldots,x_{n}\in\mathbb{R},\varphi(x_{1},\ldots
x_{n})$ where $\varphi$ is a quantifier-free formula consisting of polynomial
equations, polynomial inequalities and Boolean disjunctions and conjunctions.
The goal is to decide whether the formula is true. Then the Tarski-Seidenberg
theorem shows that the Existential Theory of the Reals is decidable, and the
following theorem provides an algorithm to decide it.

######  Theorem 2.1 ([BPR10, Theorem 3.12]).

Let $\Phi$ be the formula $\exists
x_{1},\ldots,x_{n}\in\mathbb{R},\varphi(x_{1},\ldots x_{n})$ where $\varphi$
is a quantifier-free formula consisting of polynomial equations, polynomial
inequalities and Boolean disjunctions and conjunctions. Let $s$ be the number
of equations and inequalities appearing in $\Phi$, $d$ be an upper bound on
their degrees, and $\tau$ be an upper bound on the bitsize of their
coefficients. Then there exists an algorithm running in time
$(sd)^{O(n)}\mathrm{poly}(\tau)$ that decides the truth of $\Phi$.

In particular; one can solve in polynomial time instances of the Existential
Theory of the Reals when the number of (in)equations, their degree and the
number of variables is constant. This is the case for all the instances of the
Existential Theory of the Reals in this paper. In order to ease reading, we
will often abuse language in this paper and call an instance of the
Existential Theory of the Reals simply a system of polynomial equations.

In our algorithms, we will sometimes want to extract a specific solution to a
system of polynomial equations. Such a solution is not provided by Theorem
2.1, and this runs into algebraic issues. Indeed, even for a single real
polynomial equation, there might be no rational solutions (e.g., for
$x^{2}=2$), and more generally by the Abel-Ruffini theorem shows there is in
general no solution in radicals if the degree of the equation is at least five
(this is for example the case for $x^{5}-6x-3=0$ [Cox11, Example 8.5.5]).
Nevertheless, we can encode such a solution using _real univariate
representations_. This consists of a real single-variable polynomial $f$, an
information encoding a single root $t$ of $f$ (its _Thom encoding_ [BPR10,
Definition 2.29]) and a set of real single-variable polynomials
$g_{0},\ldots,g_{k}$. Together, this data represents the point
$(\frac{g_{1}(t)}{g_{0}(t)},\ldots,\frac{g_{k}(t)}{g_{0}(t)})$ in
$\mathbb{R}^{k}$. We refer to Basu, Pollack and Roy [BPR10, Section 12.4] for
the precise definition and more background. Then Theorem 2.1 can be
strengthened [BPR10, Theorem 3.10] to not only decide if there is a solution,
but also compute a real univariate representation of a333Actually, one can
compute a point in each semi-algebraically connected component, but we will
not need this stronger fact. point in the solution set. The corresponding
algorithm also has complexity $(sd)^{O(n)}\mathrm{poly}(\tau)$ and the bitsize
of the real univariate representation is bounded by $\tau d^{O(n)}$.
Throughout this paper, we rely on this algorithm implicitly whenever we say
that we _solve_ a system of polynomial equations of constant size, and the
output is encoded by this linear-size (in $\tau$) real univariate
representation. Since this representation amounts essentially to a polynomial
equation, it can seamlessly be manipulated, and in particular we can plug it
into another system of polynomial equations of constant size, which can then
be solved again using the same algorithm.

##### Matroids.

Our algorithm for Theorem 1.2 relies on enumerating all the possible
dependencies within a constant-size subset of vectors of a near-optimal
solution. In order to do so, we rely on matroids, which are a combinatorial
structure encoding, and generalizing, the dependencies within a family of
vectors. We refer to Oxley [Oxl06] for an introduction. A _matroid_ $M$ is a
pair $(E,\mathcal{I})$ where $E$ is a finite set called the _ground set_ and
$\mathcal{I}$ is a collection of subsets of $E$ called _independent sets_
satisfying the following axioms: (i) the empty set is an independent set, (ii)
if $I^{\prime}\subseteq I$ and $I$ is an independent set, $I^{\prime}$ is an
independent set, and (iii) if $I_{1}$ and $I_{2}$ are independent sets and
$|I_{1}|<|I_{2}|$ there exists an element $e$ in $I_{2}$ such that
$I_{1}\cup\\{e\\}$ is an independent set. The _rank_ of a matroid is the
maximum size of an independent set. It is immediate from the definitions that
given a finite set of vectors in $\mathbb{R}^{k}$, the subsets of vectors
which are independent form a matroid. The converse is not true: the matroids
that correspond to vectors in $\mathbb{R}^{k}$ are called _representable over
the reals_. We can detect those by encoding dependencies as determinants and
using real-algebraic algorithms to solve the corresponding equations as
described in the previous paragraph, and in a certain technical sense this is
the best algorithm to do so [KMM23]. The number of matroids of rank $k$ on a
ground set of size $n$ is naturally upper bounded by $2^{n^{O(k)}}$.

The rigid case that we started with in Section 1.1.1 corresponds to constant-
sized sets of vectors $U$ and $W$ in $\mathbb{R}^{k}$ in which all the subsets
of size $k$ form a basis. The matroid obtained from that set is one in which
every set of $k$ elements forms an independent set, and in that setting our
algorithm is simpler. In order to handle the general case, where sets of $k$
vectors or less might not be independent, our approach requires guessing the
entire structure of linear dependencies between elements of $U$ (and $W$).
Since the vectors are over the reals, in order to do this guessing, one needs
a finite combinatorial abstraction for these dependencies: this is exactly the
information that is encoded in the matroids formed by $U$ and $W$.

##### Extremal graph theory.

The Kovari-Sòs-Turan theorem [KST54] says for any integer $k$, there exists a
constant $c_{KST}$ such that any bipartite graph with bipartitions of $n_{1}$
and $n_{2}$ vertices with at least $c_{KST}(n_{1}n_{2}^{1-1/(k+1)}+n_{2})$
edges contains a $K_{k+1,k+1}$ as a subgraph, where the constant $c_{KST}$ is
$\Theta(k)$. We will need the following supersaturated version.

######  Lemma 2.2.

For any $\varepsilon>0$ and $k\in\mathbb{N}$, there exist constants
$c^{\prime}_{KST}=(\varepsilon/k)^{\Theta(k^{2})}$ and
$n_{KST}=(k/\varepsilon)^{\Theta(k)}$ such that any bipartite graph with
bipartitions of $n_{1}$ and $n_{2}$ vertices, where $n_{1}\geq n_{2}\geq
n_{KST}$ and at least $\varepsilon n_{1}n_{2}$ edges contains at least
$c^{\prime}_{KST}n_{1}^{k+1}n_{2}^{k+1}$ copies of $K_{k+1,k+1}$ as a
subgraph.

We include a proof for completeness, it is very similar to the proof of the
classical Erdős-Simonovits [ES83] theorem.

###### Proof.

Let $n_{KST}$ denote the smallest integer so that $\varepsilon
n_{KST}^{1/(k+1)}\geq 2c_{KST}$, thus $n_{KST}=(k/\varepsilon)^{\Theta(k)}$.
For this choice of $n_{KST}$, any $n_{1}\geq n_{2}\geq n_{KST}$ satisfy
$(\varepsilon/2)n_{1}n_{2}\geq c_{KST}(n_{1}n_{2}^{1-1/(k+1)}+n_{2})$. Let $G$
denote a bipartite graph with at least $\varepsilon n_{1}n_{2}$ edges where
$n_{1}\geq n_{2}\geq n_{KST}$ denote the sizes of the bipartition.

We consider the subsets $M$ of $G$ consisting of $n_{KST}$ vertices on each
side of the bipartition. Among them, those with at least
$(\varepsilon/2)n_{KST}^{2}$ edges are called _saturated_ , and we denote
their number by $\eta\binom{n_{1}}{n_{KST}}\binom{n_{2}}{n_{KST}}$.

We double count the number of edges in $G$:

$e(G)=\frac{\sum_{M}e(G[M])}{\binom{n_{1}-1}{n_{KST}-1}\binom{n_{2}-1}{n_{KST}-1}}\leq\frac{\eta\binom{n_{1}}{n_{KST}}\binom{n_{2}}{n_{KST}}n_{KST}^{2}+(1-\eta)\binom{n_{1}}{n_{KST}}\binom{n_{2}}{n_{KST}}\varepsilon
n_{KST}^{2}}{\binom{n_{1}-1}{n_{KST}-1}\binom{n_{2}-1}{n_{KST}-1}}.$

By our assumption, $e(G)\geq\varepsilon n_{1}n_{2}$, and thus

$\varepsilon\leq\eta+(1-\eta)\varepsilon/2.$

Therefore $\eta\geq\frac{\varepsilon}{2-\varepsilon}$, i.e., the proportion of
saturated subgraphs stays bounded away from zero. Each saturated subgraph
induced by $M$ contains a $K_{k+1,k+1}$ by the Kovari-Sòs-Turan theorem, and
thus $G$ contains (accounting for the multiple counting) at least
$\frac{\eta\binom{n_{1}}{n_{KST}}\binom{n_{2}}{n_{KST}}}{\binom{n_{1}-(k+1)}{n_{KST}-(k+1)}\binom{n_{2}-(k+1)}{n_{KST}-(k+1)}}=\frac{\eta\binom{n_{1}}{k+1}\binom{n_{2}}{k+1}}{\binom{n_{KST}}{k+1}\binom{n_{KST}}{k+1}}$
different copies of them. This concludes the proof with
$c^{\prime}_{KST}=(\varepsilon/k)^{\Theta(k^{2})}$. ∎

##  3 A polynomial-time additive approximation scheme

The main result of this section is the following.

See 1.2

##### Algorithm and analysis

The algorithm is described in Figure LABEL:A:mainalgo, where we have used the
following notations. We denote by $R$ the set of row indices of $A$ and by $C$
the set of column indices. We think of the matrices $U=(u_{i,j})$ and
$W=(w_{i,j})$ as being unknowns, and thus each entry in the matrix $A$ induces
an equation $\sum_{\ell=1}^{k}u_{i,\ell}w_{j,\ell}=A_{i,j}$. Of course, in
general, in an optimal solution, not all of these equations will be satisfied.

The proof of Theorem 1.2 follows from Proposition 3.1. It is quite a bit
stronger than what is actually needed for Theorem 1.2, as this stronger
version will be required for the proof of Theorem 1.1. We actually solve a
more constrained problem, Restricted-$\ell_{0}$-Low Rank Approximation, where
we are additionally given a pair of _projection constraints_ , that is,
matrices $p_{R}$ in $\mathbb{R}^{t_{R}\times k}$ and $p_{C}$ in
$\mathbb{R}^{t_{C}\times k}$ as well as real vectors $(a_{i})_{i\in R}$ in
$\mathbb{R}^{t_{R}}$ and $(b_{j})_{j\in C}$ in $\mathbb{R}^{t_{c}}$, and we
require that the matrices $U$ and $W$ also satisfy $p_{R}(u_{i})=a_{i}$ and
$p_{C}(v_{j})=b_{j}$ for all $i$ and $j$.

The algorithm is parameterized by a large constant
$\kappa_{1}=\kappa_{1}(k,\varepsilon)$ which, as we will see later, can be
taken to be $(k/\varepsilon)^{\Theta(k^{3})}$. We define a _supercore_
$\Sigma=(R_{S},C_{S},G,M_{R_{S}},M_{C_{S}})$ as being the data enumerated in
step LABEL:step:enumeration of the algorithm: subsets $R_{S}$ and $C_{S}$ of
rows and columns of the same size, a bipartite graph on these subsets
$G=(R_{S}\cup C_{S},E)$ and a pair of rank-$k$ matroids $M_{R_{S}}$ and
$M_{C_{S}}$ on $R_{S}$ and $C_{S}$. The size of a supercore is the size of
$R_{S}$ and $C_{S}$.

######  Proposition 3.1.

Let $\varepsilon>0$ and $k\in\mathbb{N}$ be constants. There exists a constant
$\kappa_{1}=(k/\varepsilon)^{\mathrm{poly}(k)}$ such that for any $n_{R}\times
n_{C}$ matrix $A$, any pair of projection constraints, and any $n_{1}\times
n_{2}$ submatrix $A^{\prime}\subseteq A$, there exists an
$(\varepsilon/2)$-additive approximation to Restricted $\ell_{0}$-Low Rank
Approximation on $A^{\prime}$, that we call Near-OPT such that one of the
supercores $\Sigma=(R_{S},C_{S},G,M_{R},M_{C})$ of size at most $\kappa_{1}$
satisfies:

  1. (1)

The rows and columns of Near-OPT indexed by $R_{S}$ and $C_{S}$ (restricted to
$A^{\prime}$) match those of the solution computed in Step
LABEL:step:solution.

  2. (2)

The other rows and columns of Near-OPT are contained in the alphabets computed
in steps LABEL:step:alphabet1 and LABEL:step:alphabet2.

This proposition immediately implies Theorem 1.2 by using the full matrix $A$
for $A^{\prime}$ and enforcing no projection constraints on the rows and the
columns: it shows that the Max-2-CSP that we define in Step LABEL:step:Max2CSP
provides an $\varepsilon/2$-additive approximation to $\ell_{0}$-Low Rank
Approximation, and thus solving this Max-2-CSP with an
$\varepsilon/2$-additive approximation will yield the desired
$\varepsilon$-additive approximation. The complexity of the algorithm is
dominated by Step LABEL:step:enumeration, where the algorithm enumerates all
subsets of the rows and columns of size at most
$\kappa_{1}=(k/\varepsilon)^{\Theta(k^{3})}$. The other heavy computational
steps are solving the system of polynomial equations in Steps:
LABEL:step:solution, LABEL:step:alphabet1 and LABEL:step:alphabet2: the number
of equations is always upper bounded by ${\kappa_{1}^{\mathrm{poly}(k)}}$, and
thus applying Theorem 2.1 , we stay within the allowed timebound. Finally,
solving additively the Max-2-CSP instance in Step LABEL:step:densecsp can be
done in time $q^{O(\log q/\varepsilon^{2})}+\mathrm{poly}(n)$, where $q$ is an
upper bound on the size of the alphabet, which we can take to be
${\kappa_{1}^{\mathrm{poly}(k)}}$ (see [Yar14] and [MR17, Footnote 2]).

We now prove Proposition 3.1.

###### Proof.

Throughout this proof, we reason on the submatrix $A^{\prime}$. Without loss
of generality we can assume that $n_{1}\geq n_{2}$. We denote a solution to
Restricted $\ell_{0}$-Low Rank Approximation in this submatrix by $Sol=(U,W)$,
and we denote by $G$ the bipartite graph $G=(R^{\prime}\cup C^{\prime},E)$,
where $R^{\prime}$ and $C^{\prime}$ denote the indices of rows and columns of
$A^{\prime}$ and $(i,j)\in E$ if the $(i,j)$ entry of the matrix $A^{\prime}$
agrees with $(UW^{T})_{i,j}$. Initially, $Sol$ will be an optimal solution,
which we will then modify to a near-optimal solution, i.e., a
$\varepsilon/2$-additive approximation to the optimal solution.

The first step of the proof is to show that there exists a near-optimal
solution which has a nice structure for our problem. Here, “nice” means that
such a solution is parameterized by constantly many pieces, each of which can
be fully determined from a subset of constant size (its _core_).

In order to do so, we start from an optimal solution, corresponding to a graph
$G$, and define a family of pieces as follows. We consider a set $S:=R_{S}\cup
C_{S}\subset R^{\prime}\cup C^{\prime}$ of $\kappa_{2}$ rows and $\kappa_{2}$
columns, where $\kappa_{2}=\kappa_{2}(k,\varepsilon)$ is a constant to be
fixed later. The optimal solution induces a pair of rank-$k$ matroids $M_{R}$
and $M_{C}$, which restrict to submatroids $M_{R_{S}}$ and $M_{C_{S}}$ on the
sets $R_{S}$ and $C_{S}$, and, for each independent set $I\in M_{R}$
(respectively $J\in M_{C}$), there is a corresponding subspace $E_{I}$
(respectively $E_{J}$).

For each pair of independent sets $I,J$ in $M_{R_{S}}\times M_{C_{S}}$, we
define a piece $P_{I,J}$ as follows. If the complete bipartite graph on
$I\times J$ is included in $G$, we create a piece with $I\cup J$ as the core
and $I\cup I_{2}\cup J\cup J_{2}$ as the vertex set, where $J_{2}$ denotes the
set of vertices adjacent to all of $I$ in $G$ and belonging to the subspace
spanned by $J$, and $I_{2}$ denotes the set of vertices adjacent to all of $J$
in $G$ and belonging to the subspace spanned by $I$. The graph of the piece is
the subgraph of $G$ on the vertex set. The matroids on this piece are the
submatroids induced by $M_{R}$ and $M_{C}$. Note that pieces will in general
overlap.

######  Lemma 3.2.

If $\kappa_{2}=(k/\varepsilon)^{\Omega(k^{2})}$, there exists a set $S$ such
that all but at most $(\varepsilon/2)n_{1}n_{2}$ edges of $G$ belong to at
least one piece $P_{I,J}$.

###### Proof.

We distinguish two cases for the proof, depending on how $n_{2}$ compares to
$n_{KST}$, the constant of Lemma 2.2.

##### First case: $n_{2}\geq n_{KST}$.

In this case, the proof relies on the probabilistic method: the set $S$ is
taken by sampling uniformly at random a set $R_{S}$ of $\kappa_{2}$ rows and a
set $C_{S}$ of $\kappa_{2}$ columns. Let $\kappa_{3}$ be a constant depending
on $\varepsilon$ and $k$ to be fixed later. We say that an edge $e=(i,j)$ is
_efficient_ if there exists at least $\kappa_{3}n_{1}^{k}n_{2}^{k}$ copies of
$K_{k+1,k+1}$ in $G$ containing $e$ such that for each such copy, the space
spanned by (the vectors corresponding to) the other $k$ vertices in $R$
contains $i$, and the space spanned by (the vectors corresponding to) the
other $k$ vertices in $C$ contains $j$. The main claim that we prove is:

######  Claim 1.

All but at most $(\varepsilon/4)n_{1}n_{2}$ edges are efficient.

###### Proof of the claim..

We say that a $K_{k+1,k+1}$ is good for one of its edges $(i,j)$ if $i$ and
$j$ belong to the span of the other respective $k$ vertices. Let us assume
that the claim is wrong. Then there are at least $(\varepsilon/4)n_{1}n_{2}$
edges $(i,j)$ which do not belong to at least $\kappa_{3}n_{1}^{k}n_{2}^{k}$
copies of $K_{k+1,k+1}$ which are good for them. We remove all the other edges
from the graph, call the resulting graph $G^{\prime}$. Then we apply the
(supersaturated) Kovari-Sos-Turan theorem of Lemma 2.2 on this $G^{\prime}$.
The assumptions hold since by the assumption of the first case, $n_{1}\geq
n_{2}\geq n_{KST}$ and there are at least $(\varepsilon/4)n_{1}n_{2}$ edges.
It implies that that there exists
$c^{\prime}_{KST}=(\varepsilon/k)^{\Theta(k^{2})}$ such that there are at
least $c^{\prime}_{KST}n_{1}^{k+1}n_{2}^{k+1}$ copies of $K_{k+1,k+1}$ in
$G^{\prime}$. Now, observe that each copy of $K_{k+1,k+1}$ is good for at
least one of its edges. Thus, by double counting, there must be one edge
contained in $c^{\prime}_{KST}n_{1}^{k}n_{2}^{k}$ copies of $K_{k+1,k+1}$
which are good for it. This is a contradiction for $\kappa_{3}\leq
c^{\prime}_{KST}=(\varepsilon/k)^{\Theta(k^{2})}$. ∎

We now prove Lemma 3.2. We first discard the inefficient edges. Then we claim
that with probability more than $1-\varepsilon/4$, an efficient edge belongs
to a piece. In order to prove that, we partition the sample set $S$ into
$\lfloor\kappa_{2}/(2k)\rfloor$ disjoint subsets of $k$ rows and $k$ columns.
With probability at least $\kappa_{3}$, such a subset will contain the $2k$
other vertices of one of the $K_{k+1,k+1}$ defining an efficient edge. So if
$(1-\kappa_{3})^{\kappa_{2}/(2k)}\leq\varepsilon/4$, which happens if the
constant $\kappa_{2}$ sufficiently large (using the value of $\kappa_{3}$ from
the claim, we can take $\kappa_{2}=(k/\varepsilon)^{\Theta(k^{2})}$), with
probability more than $1-\varepsilon/4$ the sample will contain the $2k$ other
vertices of one of the $K_{k+1,k+1}$ defining an efficient edge.

We consider subsets $I$ and $J$ of these $2k$ vertices so that $I$ and $J$ are
independent sets, and $I$ is dependent with $i$ and $J$ is dependent with $j$.
Then the edge $e$ will belong to the piece $P_{I,J}$ since $I$ and $J$ induce
a complete bipartite graph, and thus form a core, and by definition of
efficiency, $i$ and $j$ are adjacent to all the vertices of this core. By
linearity of expectation, the expected number of edges for which this fails is
less than $(\varepsilon/4)n_{1}n_{2}$. Thus with nonzero probability, the set
$S$ has the required properties. This concludes the proof.

##### Second case: $n_{2}\leq n_{KST}$.

In that case, we even have the stronger result that there exists a choice of
$S$ such that every edge belongs to a piece. Indeed, for each column $j$,
denote by $I(j)$ the set $\\{i\in R^{\prime}\mid(i,j)\in G\\}$, and by $B(j)$
a subset of $I(j)$ so that the rows indexed by $B(j)$ form a basis of the
vector space spanned by the rows indexed by $I(j)$ in the optimal solution.
Then we consider the set of rows obtained by taking the union of all the sets
$B(j)$. We take the set $S$ to consist of the union of these rows and the
entire set of columns, which we can do if $\kappa_{2}\geq kn_{KST}$ (recall
that $n_{KST}=(k/\varepsilon)^{\Theta(k)}$). Now, each edge $(i,j)$ of $G$ is
contained in the piece $P_{B(j),\\{j\\}}$. Indeed this piece exists since by
definition the graph induced by $B(j)$ and $\\{j\\}$ in the optimal solution
is the complete bipartite graph. Furthermore, $i$ belongs to the space $B(j)$
and is adjacent to $j$, therefore it belongs to this piece.∎

From now on, we consider that the set $S$ satisfies Lemma 3.2. At the cost of
modifying the solution by $(\varepsilon/2)n_{1}n_{2}$, we can neglect the
edges not covered by Lemma 3.2, and therefore assume that all the edges (and
in particular all the vertices) are contained in some piece, which we do from
now on.

Now, we aim at controlling the interactions between different pieces
$P_{I,J}$. This is done by defining the following _auxiliary cores_ , which is
an additional set of subgraphs of $G$. Let $\mathcal{P}$ denote a set of at
most $k$ pairs of independent sets $(I,J)$ in $M_{R_{S}}\times M_{C_{S}}$. If
the intersection of all the rows in $P_{I,J}$ for $(I,J)\in\mathcal{P}$ is
non-empty, we let $I^{\prime}$ denote a subset of rows in this intersection
for which the vectors are maximally independent. Then we define an auxiliary
core whose vertex set is $I^{\prime}\cup\bigcup_{\exists
I,(I,J)\in\mathcal{P}}J$ and whose graph is the complete bipartite graph on
the vertex set. Note that by construction of a piece $P_{I,J}$, each row of
such a piece is adjacent to all the columns in $J$. Therefore, the auxiliary
core is indeed a subgraph of $G$. We also define auxiliary cores symmetrically
with the roles of rows and columns inverted.

The supercore is defined as the union of the cores of all the pieces $P_{I,J}$
and all the auxiliary cores for all sets $\mathcal{P}$ of at most $k$ pairs of
independent sets. The corresponding matroid is the one induced from the near-
optimal solution. By construction, it has size at most some constant
$\kappa_{1}$ which we can take to be
$\kappa_{2}^{\Theta(k)}=(\frac{k}{\varepsilon})^{\Theta(k^{3})}$, and we are
now ready to prove Proposition 3.1. We consider a near-optimal solution
$Sol=(U,W)$ where pieces cover all the edges, as provided by Lemma 3.2, and
denote by $G$ the graph of covered edges. We then consider an arbitrary
solution $Sys=(U_{sys},W_{sys})$ to the system of equations in Step
LABEL:step:solution0, where the correct supercore has been guessed. A solution
always exists since $Sol$ is such a solution. We will show how to extend $Sys$
to a solution of the whole set $R^{\prime}\cup C^{\prime}$ such that the set
of edges in $G$ is satisfied.

We first consider an edge $(i,j)$ that is not included in the supercore, and
such that $i$ (respectively $j$) does not belong to $R_{S}$ (respectively
$C_{S}$). In $Sol$, this edge is included in a collection of pieces $P_{I,J}$.
Each of these pieces puts two types of constraints on the value of the row
$i$: (i) it should belong to the subspace spanned by the vectors of $I$ in
$Sys$ and $(ii)$ it should satisfy the linear equations induced by the core of
$P_{I,J}$, where the values of the columns in $J$ are fixed by $W_{sys}$. The
pieces put a symmetric set of constraints on the column $j$. We claim that if
these constraints are satisfied in a solution that extends $Sys$, all the
edges of $G$ are automatically satisfied in that solution. This will follow
from this easy linear algebraic lemma.

######  Lemma 3.3.

If $M_{1}$ and $M_{2}$ are two matrices and $a$ and $b$ are two real vectors,
then for any two vectors $u$ and $w$ such that $M_{1}u=a$, $M_{2}w=b$, $u$ is
a linear combination of the columns of $M_{2}$ and $w$ is a linear combination
of the columns of $M_{1}$, the value of $\langle u,w\rangle$ is uniquely
determined.

###### Proof.

Let $u_{1},w_{1}$ and $u_{2},w_{2}$ be two pairs of vectors satisfying the
conditions of the lemma. Then since $M_{2}w_{1}=M_{2}w_{2}=b$, $w_{2}-w_{1}$
is in the kernel of $M_{2}$. Since $u_{1}$ is a linear combination of the
columns of $M_{2}$, there exists a vector $x$ such that $u_{1}=M_{2}^{T}x$,
and then $\langle u_{1},w_{2}\rangle=\langle
u_{1},(w_{1}+w_{2}-w_{1})\rangle=\langle M_{2}^{T}x,w_{1}\rangle+\langle
M_{2}^{T}x,w_{2}-w_{1}\rangle=\langle M_{2}^{T}x,w_{1}\rangle=\langle
u_{1},w_{1}\rangle$. Likewise, writing $w_{2}=M_{1}^{T}y$, $\langle
u_{2},w_{2}\rangle=\langle u_{1}+u_{2}-u_{1},M_{1}^{T}y\rangle=\langle
u_{1},w_{2}\rangle$, and thus $\langle u_{1},w_{1}\rangle=\langle
u_{2},w_{2}\rangle$. ∎

For each edge $(i,j)$ in a piece $P_{I,J}$, if we write $M_{1}u_{i}^{T}=a$ and
$M_{2}w_{j}=b$ for the linear equations of type (ii) induced respectively by
the columns and the rows of the core on the vectors $u_{i}$ and $w_{j}$, then
the conditions (i) directly imply that $u_{i}^{T}$ is a linear combination of
the columns of $M_{2}$ and $w_{j}$ is a linear combination of the columns of
$M_{1}$. Therefore, by Lemma 3.3, the value of $\langle u_{i},w_{j}\rangle$,
which determines whether the edge $(i,j)$ is satisfied, is unique, and in
particular is equal to its value in $Sol$, where it is satisfied by definition
of an edge of $G$.

So in order to satisfy all the edges of $G$, it suffices to extend $Sys$ to a
solution of the whole set $R^{\prime}\cup C^{\prime}$ such that

  1. (i)

the linear dependencies between a row and the rows of the cores are the same
as in $Sol$,

  2. (ii)

the linear dependencies between a column and the columns of the cores are the
same as in $Sol$,

  3. (iii)

for any row $i$, all the edges to the core columns of pieces that $i$ belongs
to are satisfied,

  4. (iv)

for any column $j$, all the edges to core rows of pieces that $j$ belongs to
are satisfied,

  5. (v)

in the restricted case, the additional projection constraints are satisfied.

We claim that this can always be done. Let $i$ be a row that belongs to a set
of pieces $\\{P_{I,J}\\}$, and denote by $\mathcal{P}$ the corresponding set
of pairs of independent sets. Since the constraints induced by each piece
$P_{I,J}$ are linear and the row $i$ belongs to $\mathbb{R}^{k}$, there exists
a subset $\mathcal{P}^{\prime}$ of $\mathcal{P}$ of size at most $k$ inducing
exactly the exact same constraints as $\mathcal{P}$ on the row $i$.

We consider the system of equations in Step LABEL:step:alphabet1 obtained by
taking for $\Phi$ the set of independent sets involved in
$\mathcal{P}^{\prime}$. We directly have that any solution to these system of
equations satisfy the constraints above corresponding to rows. So there
remains to show that this system of equations has a solution. This is
immediate for a row $i$ that belongs to the core of one of the pieces or to
the auxiliary core corresponding to $\mathcal{P}^{\prime}$.

Otherwise, we denote by $I^{\prime}$ the set of rows of the auxiliary core
corresponding to $\mathcal{P}^{\prime}$. We denote by $u^{*}_{i}$ and
$w^{*}_{j}$ the vectors of $Sol$, and by $u_{i}$ and $w_{j}$ the row and
vectors obtained as a solution of the system of equations in Step
LABEL:step:solution. By definition, in the solution $Sol$ the row $i$ belongs
to the space spanned by the rows $I^{\prime}$, therefore we can write
$u^{*}_{i}=\sum_{\ell\in I^{\prime}}\alpha_{\ell}u^{*}_{\ell}$, for some
family of real numbers $\alpha_{\ell}$. We want to show that there exists
$u_{i}$ for the row $i$ with the following constraints: (i) the inner products
induced by edges with the columns of the cores of the pieces $P_{I,J}$ that
$i$ belongs to are satisfied, (ii) $u_{i}$ belongs to the space spanned by the
row vectors in $Sys$ indexed by $I^{\prime}$ and (iii) in the restricted case,
$u_{i}$ satisfies the projection constraint $p_{R}(u_{i})=b_{i}$. We consider
the vector $u_{i}:=\sum_{\ell\in I^{\prime}}\alpha_{\ell}u_{\ell}$ and claim
that it satisfies all three constraints. It trivially satisfies (ii). For any
column $j$ in a piece $P_{I,J}$ in $\mathcal{P}^{\prime}$, we have

$\displaystyle\langle u_{i},w_{j}\rangle=$ $\displaystyle\langle\sum_{\ell\in
I^{\prime}}\alpha_{\ell}u_{\ell},w_{j}\rangle=\sum_{\ell\in
I^{\prime}}\alpha_{\ell}\langle u_{\ell},w_{j}\rangle=\sum_{\ell\in
I^{\prime}}\alpha_{\ell}\langle u_{\ell},w_{j}\rangle=\sum_{\ell\in
I^{\prime}}\alpha_{\ell}A_{\ell,j}$ $\displaystyle=$
$\displaystyle\sum_{\ell\in I^{\prime}}\alpha_{\ell}\langle
u^{*}_{\ell},w_{j}^{*}\rangle=\langle u^{*}_{i},w_{j}^{*}\rangle=A_{i,j}.$

By definition of $\mathcal{P}^{\prime}$, the constraints induced by the pieces
in $\mathcal{P}\setminus\mathcal{P^{\prime}}$ are also satisfied. For
condition (iii), we have similarly

$\displaystyle p_{R}(u_{i})=\sum_{\ell\in
I^{\prime}}\alpha_{\ell}p_{R}(u_{\ell})=\sum_{\ell\in
I^{\prime}}\alpha_{\ell}b_{\ell}=\sum_{\ell\in
I^{\prime}}\alpha_{\ell}p_{R}(u^{*}_{\ell})=p_{R}(u^{*}_{i})=$ $\displaystyle
b_{i}$

Symmetrically, we can always find a solution to all the constraints for any
column $j$. Therefore, we can extend $Sys$ to a solution that is at least as
good as $Sol$, and is thus at least a $\varepsilon/2$-additive approximation
to Restricted $\ell_{0}$-Low Rank Approximation on $A^{\prime}$. This
concludes the proof of the proposition. ∎

##  4 A polynomial-time multiplicative approximation scheme

In this section, we prove our main theorem, which gives a multiplicative PTAS
for $\ell_{0}$-Low Rank Approximation.

See 1.1

###### Proof.

Let $A\in\mathbb{R}^{n_{R}\times n_{C}}$ be the input matrix. Let $UW^{T}$ be
an optimal solution where $U\in\mathbb{R}^{n_{R}\times k}$ and
$W\in\mathbb{R}^{n_{C}\times k}$. We assume that the rank of $UW^{T}$ is
exactly $k$; otherwise one can solve for a smaller rank (there are only $k+1$
possibilities). Let $u_{i}$ be the $i$th row of $U$ and $w_{i}$ be the $i$th
row of $W$ (as column vectors). Let $OPT=|\\{(i,j):A_{i,j}\neq\langle
u_{i},w_{j}\rangle\\}|$ be the number of errors that the optimal solution
makes.

We will define several constants depending on $\varepsilon_{0}$ and $k$ (and
each other) and see their dependencies at the end of the proof. Let
$\delta_{0}:=1/20k$ be such a constant. We first partition $[n_{C}]$ to
$\ell_{C}$ layers $J_{1},\dots,J_{\ell_{C}}$ with $\ell_{C}\leq k$. The
desired properties for the layers (called the layer properties) are as
follows. For $J\subseteq[n_{C}]$, let $W(J):=\\{w_{q}:q\in J\\}$ be the set of
vectors corresponding to $J$ as a multiset (so that $|W(J)|=|J|$).

  1. i.

$J_{1},\dots,J_{\ell_{C}}$ partition $[n_{C}]$ with
$|J_{j}|\leq(2k\delta_{0})|J_{j-1}|=|J_{j-1}|/10$.

  2. ii.

$\emptyset=T_{J,0}\subseteq T_{J,1}\subseteq\dots\subseteq
T_{J,{\ell_{C}}}=\mathbb{R}^{k}$ are subspaces such that for any
$j\in[\ell_{C}]$, $W(J_{j})\subseteq T_{J,j}$.

  3. iii.

For any $j\in[\ell_{C}]$, no subspace $T^{\prime}$ with $T_{J,{j-1}}\subseteq
T^{\prime}\subsetneq T_{J,j}$ satisfies $|W(J_{j})\cap
T^{\prime}|>(1-\delta_{0})|J_{j}|$.

The following lemma shows the existence of such layers. Note that the layers
are used only in the analysis so that the algorithm does not need to construct
them.

######  Lemma 4.1.

There exist $J_{1},\dots,J_{\ell_{C}}$ with $\ell_{C}\leq k$ satisfying the
conditions above.

###### Proof.

For $j=1,\dots$, we will maintain that $M_{j}\subseteq[n_{C}]$ and subspace
$T_{J,j}\subseteq\mathbb{R}^{k}$ that satisfies $W(M_{j})=W([n_{C}])\setminus
T_{J,j-1}$ for each $j\geq 1$. Let $M_{1}=[n_{C}]$, $T_{J,0}=\emptyset$, and
$j=1$, and run the following algorithm.

  1. 1.

Call a subspace $T$ with $T_{J,j-1}\subsetneq T\subseteq\mathbb{R}^{k}$ full
if no proper subspace $T_{J,j-1}\subseteq T^{\prime}\subsetneq T$ has
$|T^{\prime}\cap W(M_{j})|\geq(1-\delta_{0})|T\cap W(M_{j})|$. (Note that
every $T$ with $\dim(T)\leq\dim(T_{j-1})+1$ is full, since $|T_{J,j-1}\cap
W(M_{j})|=0$.)

  2. 2.

Choose a full subspace $T_{J,j}$ that contains the maximum number of vectors
from $W(M_{j})$. Let $J_{j}\subseteq M_{j}$ be the set of columns whose
vectors belong to $T_{J,j}$, and $M_{j+1}=M_{j}\setminus J_{j}$. In
particular, $W(J_{j})=(T_{J,j}\setminus T_{J,j-1})\cap W([n_{C}])$.

  3. 3.

If $M_{j+1}=\emptyset$, halt. Otherwise, $j\leftarrow j+1$ and go to Line 1.

Since the dimension of $T_{J,j}$ is strictly increasing in each iteration, the
above algorithm halts before $j=\ell_{C}\leq k$ iterations. Let us check that
$J_{j}$’s and $T_{J,j}$’s satisfy the three properties for the layers.
Property i. By construction $J_{1},\dots,J_{\ell_{C}}$ partition $[n_{C}]$.
Note that also
$|J_{j}|\geq|M_{j}|(1-\delta_{0})^{k}\geq|M_{j}|(1-k\delta_{0})\geq\frac{1-k\delta_{0}}{k\delta_{0}}|J_{j+1}|\geq\frac{1}{2k\delta_{0}}|J_{j+1}|$;
one can show the existence of a full subspace $T_{J,j}$ with large $|J_{j}|$
by starting from $T=\mathbb{R}^{k}$, and if $T$ is not full, recursively going
to the a strict subspace by losing a factor $(1-\delta_{0})$ in size.

Property ii. Since we maintain $W(M_{i})\cap T_{J,j-1}=\emptyset$ and define
$J_{j}$ be the set of columns of $M_{j}$ whose vectors belong to $T_{J,j}$, we
have $W(J_{j})\subseteq T_{J,j}$ for every $j$.

Property iii. Since we chose $T_{J,j}$ to be a full space given $M_{j}$ and
$T_{J,j-1}$, there is no $T^{\prime}$ with $T_{J,j-1}\subseteq
T^{\prime}\subsetneq T_{J,j}$ that contains more than a $(1-\delta_{0})$
fraction of $J_{j}$. ∎

Apply the lemma for the rows as well to get the partition
$I_{1},\dots,I_{\ell_{R}}$ with the subspaces $T_{I,1},\dots,T_{I,\ell_{R}}$
for some $\ell_{R}\leq k$. Call $B_{i,j}:=I_{i}\times J_{j}$ the $(i,j)$th
block. Then we have $\ell_{R}\times\ell_{C}$ blocks. By guessing, suppose the
algorithm knows all block sizes and $OPT$. (There are $n^{O(k)}$
possibilities).

Let $\varepsilon_{1}>0$ be a constant to be determined. Call $B_{i,j}$ clean
if $|I_{i}||J_{j}|>OPT/\varepsilon_{1}$, dirty if
$|I_{i}||J_{j}|<\varepsilon_{1}OPT$, and half-clean otherwise. Since the
algorithm guessed $OPT$ and the block sizes, the algorithm knows which blocks
are clean/dirty/half-clean.

Now we describe our algorithm. Note that currently the algorithm has no
information about the initial optimal solution $U$ and $W$. While describing
the algorithm, we will also transform $U$ and $W$ such that (1) the
transformed solution is still near-optimal, and (2) the algorithm acquires
more information about them as it proceeds.

We divide the algorithm into four phases. The goal of the first three phases
is to construct a polynomial-size alphabet set
$\Sigma_{p}\subseteq\mathbb{R}^{k}$ for each row $p\in[n_{R}]$ and
$\Sigma_{q}\subseteq\mathbb{R}^{k}$ for each column $q\in[n_{C}]$ such that
there is a near-optimal solution where each row and column gets its vector
from its alphabet set; this corresponds to reducing to a finite-alphabet CSP.
Then the fourth phase obtains a PTAS similarly to finite-alphabet CSPs.

##### Phase 1: Obtaining initial samples.

Let $\delta_{1}$ and $t_{0}$ be other constants to be determined. For each
$j\in[\ell_{C}]$, sample $s_{j,1},\dots,s_{j,t_{0}}$ uniformly at random from
$J_{j}$; throughout the proof, the sampling is only used to show the existence
of good samples. The algorithm will enumerate all possible choices of samples.
(As the algorithm does not know $J_{j}$, it cannot perform the actual
sampling.) Similarly, for each $i\in[\ell_{R}]$, sample
$r_{i,1},\dots,r_{i,t_{0}}$ uniformly at random from $I_{i}$. Call them
initial samples. We will call them perfect if the following four bad events do
no occur.

  1. 1.

$A_{r_{i,p},s_{j,q}}\neq\langle u_{r_{i,p}},w_{s_{j,q}}\rangle$ for some clean
$B_{i,j}$ and $p,q\in[t_{0}]$; it happens with probability at most
$\varepsilon_{1}k^{2}t_{0}^{2}$. Therefore, by requiring that

$\varepsilon_{1}k^{2}t_{0}^{2}\leq\delta_{1}/4,$ (1)

this event happens with probability at most $\delta_{1}/4$.

  2. 2.

For some $i\in[\ell_{R}]$, the sampled row vectors
$\\{u_{r_{i^{\prime},p}}\\}_{i^{\prime}\in[i],p\in[t_{0}]}$ do not contain a
basis of $T_{I,i}$. We will ensure

$t_{0}\geq 2k^{2}\log(1/\delta_{1})/\delta_{0},$ (2)

which implies that this bad event happens with probability at most
$\delta_{1}/4$; assuming that the currently sampled points span some subspace
$T^{\prime}$ with $T_{I,i-1}\subseteq T^{\prime}\subsetneq T_{I,i}$, the
fullness of $T_{I,i}$ ensures that the probability of a new sample from
$I_{i}$ strictly increasing the dimension of the span is at least
$\delta_{0}$, so that the probability that a group of
$2k\log(1/\delta_{1})/\delta_{0}$ samples do not increase the dimension is at
most

$(1-\delta_{0})^{(2k\log(1/\delta_{1})/\delta_{0})}\leq
e^{-(2k\log(1/\delta_{1}))}=\delta_{1}^{2k}.$

The union bound over $k$ groups (note that $t_{0}$ is large enough to have $k$
separate groups even within a single $I_{i}$) shows that the overall failure
probability is at most $k\delta_{1}^{2k}\leq\delta_{1}/4$ whenever
$\delta_{1}$ is smaller than some universal threshold.

  3. 3.

Same as 2, but for columns. Similarly, the failure probability is at most
$\delta_{1}/4$.

  4. 4.

There exists $j\in[\ell_{C}]$ and an affine subspace $T^{\prime}$ of $T_{J,j}$
such that

$\bigg{|}\frac{|\\{q\in J_{j}:w_{q}\in
T^{\prime}\\}|}{|J_{j}|}-\frac{|\\{q\in[t_{0}]:w_{s_{j,q}}\in
T^{\prime}\\}|}{t_{0}}\bigg{|}>\tau$

for some constant $\tau$ to be determined. If it does not happen, say that the
samples $\\{s_{j,q}\\}_{j,q}$ are $\tau$-good for the layers
$T_{J,1},\dots,T_{J,\ell_{C}}$. There are infinitely many affine subspaces,
but their VC dimension is at most $k+1$; if $S\subseteq\mathbb{R}^{k}$ is any
set of $k+2$ points, $S$ cannot be shattered by affine subspaces, because
there exists $x\in S$ that can be expressed as an affine combination of
$S^{\prime}\subseteq S\setminus\\{x\\}$, which means that no affine subspace
can contain $S^{\prime}$ and exclude $x$. Therefore, by the standard sampling
guarantee for set systems with bounded VC dimensions [FM06], by taking

$t_{0}=\Omega\big{(}\frac{k}{\tau^{2}}\log(1/\tau)+\log(1/\delta_{1})\big{)},$
(3)

one can ensure that the samples are $\tau$-good with probability at least
$1-\delta_{1}/4$.

For the rest of Phase 1 and Phase 2, we condition on the event that the
initial samples are perfect. Let $d_{i}=\dim(T_{I,i})-\dim(T_{I,i-1})$ with
$d_{1}:=\dim(T_{1})$. By guessing (at most $2^{O(kt_{0}\log t_{0})}$ choices)
and reordering, the algorithm knows that for every $i\in[\ell_{R}]$,
$\\{r_{i^{\prime},p}\\}_{i^{\prime}\in[i],p\in[d_{i^{\prime}}]}$ forms a basis
of $T_{I,i}$. Order these $k$ rows
$\\{r_{i^{\prime},p}\\}_{i^{\prime}\in[\ell_{R}],p\in[d_{i^{\prime}}]}$
lexicographically in terms of $(i^{\prime},p)$ and call them
$r_{1},\dots,r_{k}\in[n_{R}]$. Let us denote by $(e_{i})_{i\in[k]}$ the
standard basis of $\mathbb{R}^{k}$, and let $C\in\mathbb{R}^{k\times k}$ be
the invertible matrix such that $(u_{r_{i}})^{T}C=(e_{i})^{T}$ for $i\in[k]$,
and let $U\leftarrow U\times C$ and $W\leftarrow W\times(C^{-1})^{T}$. Then
the new $U,W$ still remain an optimal solution. Note that this transformation
also ensures that
$T_{I,i}=\\{\mathrm{span}(e_{1},\dots,e_{\dim(T_{I,i})})\\}$.

This means that the algorithm knows $u_{r_{i}}$ for every $i\in[k]$ and
$T_{I,i}$ for every $i\in[\ell_{R}]$. Moreover, for any
$i,j\in[\ell_{R}]\times[\ell_{C}]$ with clean $B_{i,j}$, using the fact that
$A_{r_{i,p},s_{j,q}}=\langle u_{r_{i,p}},w_{s_{j,q}}\rangle$ for every
$p,q\in[t_{0}]$, the algorithm can determine the projection of $w_{s_{j,q}}$’s
to $T_{I,i}$ (denoted by $w_{s_{j,q}}|_{T_{I,i}}$). Let $T_{i,j}$ be $T_{J,j}$
projected to $T_{I,i}$. Using the fact that the column samples also span their
respective subspaces, this also implies that the algorithm knows $T_{i,j}$ for
all clean $B_{i,j}$.

##### Phase 2: Handling clean hyperblocks.

Let $\delta_{2}>0$ be a constant to be determined. Say $J_{j}$ and $J_{j+1}$
are super-separated if $|J_{j+1}|<\delta_{2}|J_{j}|$. Call $J_{i}\cup
J_{i+1}\cup\dots\cup J_{j}$ a superlayer if $J_{i}$ is super-separated from
$J_{i-1}$ (or $J_{i}=1$), $J_{j}$ is super-separated from $J_{j+1}$ (or
$J_{j}=\ell_{C}$), and no $J_{j^{\prime}}$ and $J_{j^{\prime}+1}$ are super-
separated for $j^{\prime}=i,\dots,j-1$; in words, it is the union of maximally
contiguous non-super-separated layers. Define similarly for rows. Then a
superblock is the product of a row superlayer and a column superlayer. For
instance, if rows and columns have $t_{R}$ and $t_{C}$ super-separations
respectively, the number of superblocks will be $(t_{R}+1)\times(t_{C}+1)$.
Call a superblock clean if all blocks there are clean, dirty if all blocks are
dirty, and half-clean otherwise. We will ensure

$\delta_{2}<\varepsilon_{1}^{2}$ (4)

so that if a superblock ${\cal B}\subseteq[n_{R}]\times[n_{C}]$ is half-clean,
then any superblock dominated by it is dirty; a superblock ${\cal B}^{\prime}$
is dominated by ${\cal B}$ if for any $(i,j)\in{\cal B}$ and
$(i^{\prime},j^{\prime})\in{\cal B}^{\prime}$, $i<i^{\prime}$ and
$j<j^{\prime}$.

Consider the set of superblocks that are half-clean. Say two superblocks are
adjacent if they share the set of rows or the set of columns. Finally,
consider a connected component of half-clean superblocks with this definition
of adjacency. For each such component, create a half-clean hyperblock whose
row (column) set is the union of all the row (column) sets of its superblocks.
It is clear from the construction that each row and column belongs to at most
one half-clean hyperblock. (I.e., their row sets, possibly with the set of
rows with all clean blocks and the set of rows with all dirty blocks,
partition $[n_{R}]$). Use these partitions of rows and columns to create other
hyperblocks too, and call them clean (dirty) if all blocks are clean (dirty).
See Figure 3 for an example.

Figure 3: Blocks, superblocks, and hyperblocks are divided by dotted, thin
solid, and thick solid lines respectively. The number of blocks, superblocks,
and hyperblocks are $16\times 16$, $8\times 8$, and $4\times 3$ respectively.
Clean/dirty/half-cleanness are drawn with respect to superblocks; empty cells
are clean, half-shaded cells are half-clean, and full-shaded cells are dirty.

Of course, a half-clean hyperblock may contain a clean superblock that might
be larger than $OPT$. But the following simple claim shows that its size can
be still bounded.

######  Claim 2.

Let $\mathfrak{B}$ be a half-clean hyperblock. Then its size is at most
$OPT/(\delta_{2}^{O(k^{2})}\varepsilon_{1}^{O(k)})$.

###### Proof.

Let $J^{\prime}_{1},\dots,J^{\prime}_{d_{C}}$ and
$I^{\prime}_{1},\dots,I^{\prime}_{d_{R}}$ be the layers comprising
$\mathfrak{B}$, ordered as usual from left to right and top to bottom (e.g,
$\mathfrak{B}=(\cup_{i\in[d_{R}]}I^{\prime}_{i})\times(\cup_{j\in[d_{C}]}J^{\prime}_{j})$).
We will show that
$|J^{\prime}_{d_{C}}|\geq|J^{\prime}_{1}|\delta_{2}^{O(k^{2})}(\varepsilon_{1})^{k}$.
Applying this to the rows and observing that some blocks are half-clean or
dirty implies the claim.

If $J^{\prime}_{j}$ and $J^{\prime}_{j+1}$ are in the same superlayer, their
sizes differ by a factor at most $1/\delta_{2}$. If $J^{\prime}_{j}$ and
$J^{\prime}_{j+1}$ are in different superlayers, there exist adjacent half-
clean superblocks ${\cal B}=I^{\prime}_{i}\times J^{\prime}_{j}$ and ${\cal
B}^{\prime}=I^{\prime}_{i}\times J^{\prime}_{j+1}$ within $\mathfrak{B}$ who
share the rows. (So ${\cal B}$ is on the left of ${\cal B}^{\prime}$.) Let $B$
be the bottom-right (or smallest) block in ${\cal B}$, and $B^{\prime}$ be the
top-left (or largest) block in ${\cal B}^{\prime}$. Since both ${\cal B}$ and
${\cal B}^{\prime}$ are half-clean, $B$ is dirty or half-clean and
$B^{\prime}$ is clean or half-clean, which means that the size of $B^{\prime}$
is at least $\varepsilon_{1}^{2}$ times the size of $B$. Since their
superblocks share the set of rows, the number of rows of $B$ and $B^{\prime}$
differ by a factor at most $1/\delta_{2}^{k}$, which means that the number of
columns of $B^{\prime}$ is at least $\delta_{2}^{k}\varepsilon_{1}^{2}$ times
that of $B$. ∎

For $i\in[\ell_{R}]$, let $m(i)\in[\ell_{C}]$ be the largest $j$ such that
$B_{i,j}$ belongs to a clean hyperblock ($0$ if it belongs to no clean
hyperblock). Also, given $i\in[\ell_{R}]$, let $[i]\in[\ell_{R}]$ be the
largest index such that $m(i)=m([i])$. For example, if
$i,i^{\prime}\in[\ell_{R}]$ belongs to the same hyperblock, then
$[i]=[i^{\prime}]$ and $m(i)=m(i^{\prime})$. Define $m(j)$ and $[j]$ for
$j\in[\ell_{C}]$ symmetrically. Note that, by guessing the cleanness and size
of each block, the algorithm already knows $m(i)$ for each row and column.

For each row $p\in[n_{R}]$ and $i\in[\ell_{R}]$, we let the column samples
$\\{s_{j,q}\\}_{j\in[m(i)],q\in[t_{0}]}$ vote for the projection of $u_{p}$ to
$T_{[i],m(i)}$ and call the winner $u_{p,i}$. Formally,

$u_{p,i}:=\underset{u\in
T_{[i],m(i)}}{\mathrm{argmin}}\sum_{j=1}^{m(i)}|\\{q\in[t_{0}]:A_{p,s_{j,q}}\neq\langle
u,w_{s_{j,q}}|_{T_{[i],j}}\rangle\\}|\cdot(|J_{j}|/t_{0}),$

where ties are broken arbitrarily. It can be computed in time $n^{O(k)}$, by
guessing a subset of at most $k$ samples $X$ that satisfy
$A_{p,s_{j,q}}=\langle u,w_{s_{j,q}}|_{T_{[i],j}}\rangle$ for all $s_{j,q}\in
X$, and trying $u$ that is a solution of the resulting system of linear
equations (at most $k$ linearly independent linear equations will uniquely
determine $u$). Since the definition involves only $m(i)$ and $[i]$ instead of
$i$, if $i$ and $i^{\prime}$ belong to the same hyperblock, then
$u_{p,i}=u_{p,i^{\prime}}$, so algorithmically one can compute only one row
from each hyperblock. (For simplicity, we still treat them separately.)

Having computed $u_{p,i}$’s, the algorithm’s ideal situation would be to have
$u_{p,i}=u_{p}|_{T_{[i],m(i)}}$ if $p\in I_{i}$. Of course, this cannot happen
always, but we will conduct the following transformation that forces it.

  * •

For every $p\in[n_{R}]$, let $i\in[\ell_{R}]$ such that $p\in I_{i}$.

    * –

If $u_{p,i}$ is indeed the projection of $u_{p}$ to $T_{[i],m(i)}$, then do
not change anything.

    * –

Otherwise, say $p$ is mistaken and let $u_{p}\leftarrow u_{p,i}$. By doing
this, we (conservatively) make every entry $A_{p,q}$ with $q\in J_{j}$ and
$j>m(i)$ incorrect.

The heart of this phase is to show that this transformation of $U$ ensures
that the solution pair $(U,W)$ is still near-optimal. In order to show this,
we use the following crucial lemma on the voting. It will be also used in
Phase 4.

######  Lemma 4.2.

Given parameters $\delta_{0}$, $\tau<\delta_{0}/100$, $\varepsilon>0$,
$k,\ell\in{\mathbb{N}}$, there exists
$t\leq\mathrm{poly}(k\ell/(\varepsilon\delta_{0}))\in{\mathbb{N}}$ such that
the following is true. Let $x^{*},u_{1},\dots,u_{n}\in\mathbb{R}^{k}$ where
$[n]$ is partitioned into $N_{1},\dots,N_{\ell}$ with the associated subspaces
$T_{1},\dots,T_{\ell}=\mathbb{R}^{k}$ that satisfy the layer conditions (with
parameter $\delta_{0}$). Suppose that the following information is given.

  * •

$a_{p}\in\mathbb{R}$ is given for every $p\in[n]$.

  * •

$n_{i}:=|N_{i}|$ for every $i\in[\ell]$.

  * •

For each $j\in[\ell]$, $t$ uniformly random samples $s_{j,1},\dots,s_{j,t}\in
N_{j}$ along with $u_{s_{j,1}},\dots,u_{s_{j,t}}$.

Given the information, $x\in\mathbb{R}^{k}$ is chosen to be the vector
minimizing $\sum_{j=1}^{\ell}(n_{j}/t)\cdot|\\{p\in[t]:a_{s_{j,p}}\neq\langle
x,u_{s_{j,p}}\rangle\\}|$. (Ties are broken arbitrarily.) Suppose that the
samples are $\tau$-good for $T_{1},\dots,T_{\ell}$ with probability at least
$1/2$. Then, conditioned on the event that they are $\tau$-good, the following
holds.

  * •

$\Pr[x\neq x^{*}]\leq O\big{(}\frac{OPT}{\delta_{0}n_{\ell}}\big{)}$, where
$OPT:=|\\{p\in[n]:a_{p}\neq\langle x^{*},u_{p}\rangle\\}|$.

  * •

$\mathbb{E}[|\\{p\in[n]:a_{i}\neq\langle
x,u_{p}\rangle\\}|]\leq(1+\varepsilon+O(\tau/\delta_{0}))OPT$.

For each $p\in[n_{R}]$ and $i\in[\ell_{R}]$, we apply Lemma 4.2 with
$\varepsilon\leftarrow\varepsilon_{0}/16$, $\ell\leftarrow m(i)$,
$N_{j}\leftarrow J_{j}$ (so that $[n]\leftarrow J_{1}\cup\dots\cup
J_{m(i)})$), $T_{j}\leftarrow T_{[i],j}$, $\mathbb{R}^{k}\leftarrow
T_{[i],m(i)}$, $x^{*}\leftarrow u_{p}|_{T_{[i],m(i)}}$, and
$u_{s_{j},q}\leftarrow w_{s_{j},q}|_{T_{[i],j}}$. (Since $B_{[i],j}$ is clean
for every $j\in[m(i)]$, $w_{s_{j},q}|_{T_{[i],j}}$ is known by the algorithm.)
The layer conditions for $T_{[i],j}$ will be satisfied since $T_{J,j}$’s
satisfy the layer conditions, and $T_{[i],j}$’s are their projections to
$T_{I,[i]}$.

Note that the lemma assumes we have the correct values of $x^{*}$ and
$u_{s_{j},q}$’s, which happens if the initial samples are perfect. Therefore,
given that the initial samples are perfect, which happens with probability at
least $1-\delta_{1}$, for each $p\in[n_{R}]$ and $i\in[\ell_{C}]$ with $p\in
I_{i}$, the probability that $p$ is mistaken is at most
$O(OPT_{p}/(\delta_{0}|J_{m(i)}|))/(1-\delta_{1})=O(OPT_{p}/(\delta_{0}|J_{m(i)}|))$,
where $OPT_{p}$ denotes the number of errors in row $p$ before the
transformation, which makes the expected number of additional errors in half-
clean and dirty hyperblocks due to the transformation bounded by

$\displaystyle\sum_{i\in[\ell_{R}]}\sum_{p\in
I_{i}}O\bigg{(}\frac{OPT_{p}}{\delta_{0}|J_{m(i)}|}\bigg{)}\bigg{(}\sum_{j^{\prime}=m(i)+1}^{\ell_{C}}|J_{j^{\prime}}|\bigg{)}\leq\sum_{i\in[\ell_{R}]}\sum_{p\in
I_{i}}O\bigg{(}\frac{OPT_{p}}{\delta_{0}|J_{m(i)}|}\delta_{2}|J_{m(i)}|\bigg{)}$
$\displaystyle\leq$
$\displaystyle\sum_{p\in[n_{R}]}OPT_{p}O(\delta_{2}/\delta_{0})\leq
O((\delta_{2}/\delta_{0})OPT),$

where the first inequality follows from the fact that $J_{m(i)}$ and
$J_{m(i)+1}$ are super-separated. (They are in different hyperblocks.)

The second guarantee of the lemma ensures that the total expected errors from
clean hyperblocks is at most
$(1+\varepsilon_{0}/16+O(\tau/\delta_{0}))/(1-\delta_{1})$ times the number of
original errors in those blocks. Therefore, given that the initial samples are
perfect, the expected error of the transformed solution $U,W$ is
$(1+\varepsilon_{0}/16+O(\tau/\delta_{0}+\delta_{2}/\delta_{0}))(1+2\delta_{1})OPT$.

Now we do the almost same for columns to compute $w_{q,j}$ for each
$q\in[n_{C}]$ and $j\in[\ell_{C}]$. Sample fresh rows from $I_{i}$’s, and for
each $q\in[n_{C}]$ and $j\in[\ell_{C}]$, let them vote for
$w_{q,j}|_{T_{m(j),[j]}}$. The only difference, which is indeed a
simplification, is that we do not worry about the fresh samples being perfect,
because when $p\in I_{i}$ is sampled, then the algorithm can use
$u_{p,i}=u_{p}|_{T_{[i],m(i)}}$ to get the correct projection of $u_{p}$ to
$T_{i,j}$ whenever $B_{i,j}$ is clean. This will result in transforming $W$,
but the same analysis shows that the expected error is at most
$(1+\varepsilon_{0}/8+O(\tau/\delta_{0}+\delta_{2}/\delta_{0}))(1+4\delta_{1})OPT$.
Since the algorithm actually tries all possible choices of samples and other
relevant information, this analysis implies that for some choice of samples
and correct guesses, the algorithm computed $u_{p,i}$ and $w_{q,j}$ with the
guarantees above.

##### Phase 3: Handling half-clean hyperblocks.

In Phase 1 and 2, the algorithm constructed a good (partial) vector for each
row and column; if each $p\in[n_{R}]$ chooses $u_{p,i}\in T_{[i],m(i)}$ with
$p\in I_{i}$ and if each $q\in[n_{C}]$ chooses $w_{q,j}\in T_{m(j),[j]}$ with
$q\in J_{j}$, the resulting solution gives a good approximation in clean
hyperblocks.

Consider an entry $(p,q)$ that belongs to a clean hyperblock with $p\in I_{i}$
and $q\in J_{j}$, which means that $[i]\leq m(j)$ and $[j]\leq m(i)$. When we
extend $u_{p,i}$ from $T_{[i],m(i)}$ to $T_{I,[i]}$ while ensuring that the
projection to $T_{[i],m(i)}$ is preserved, and extend $w_{q,j}$ from
$T_{m(j),[j]}$ to $T_{J,[j]}$ while ensuring that the projection to
$T_{m(j),[j]}$ is preserved, we claim that the inner product between them does
not depend on the extensions.

######  Claim 3.

If $u_{p,i}\in T_{I,{[i]}}$ and $w_{q,j}\in T_{J,[j]}$ with $[i]\leq m(j)$ and
$[j]\leq m(i)$, then $\langle u_{p,i},w_{q,j}\rangle=\langle
u_{p,i}|_{T_{[i],m(i)}},w_{q,j}|_{T_{m(j),[j]}}\rangle.$

###### Proof.

For $T\subseteq S\subseteq\mathbb{R}^{k}$, let $S/T:=\\{v\in S:\langle
v,u\rangle=0\mbox{ for all }v\in T\\}$. First we write the inner product as

$\langle u_{p,i},w_{q,j}\rangle=\langle
u_{p,i}|_{T_{[i],m(i)}},w_{q,j}\rangle+\langle
u_{p,i}|_{T_{I,[i]}/T_{[i],m(i)}},w_{q,j}\rangle.$

By definition, $u_{p,i}|_{T_{I,[i]}/T_{[i],m(i)}}$ is a vector in $T_{I,[i]}$
orthogonal to every vector in $T_{[i],m(i)}$. Since $T_{[i],m(i)}$ is the
projection of $T_{J,m(i)}$ to $T_{I,[i]}$ and $w_{q,j}\in T_{J,[j]}$ with
$[j]\leq m(i)$, the projection of $w_{q,j}$ to $T_{I,[i]}$ belongs to
$T_{[i],m(i)}$ as well, which means that $\langle
u_{p,i}|_{T_{I,[i]}/(T_{[i],m(i)})},w_{q,j}\rangle=0$. So the inner product
can be further written as

$\langle u_{p,i},w_{q,j}\rangle=\langle
u_{p,i}|_{T_{[i],m(i)}},w_{q,j}\rangle=\langle
u_{p,i}|_{T_{[i],m(i)}},w_{q,j}|_{T_{m(j),[j]}}\rangle+\langle
u_{p,i}|_{T_{[i],m(i)}},w_{q,j}|_{\mathbb{R}^{k}/T_{m(j),[j]}}\rangle.$

Since $T_{m(j),[j]}$ is the projection of $T_{J,[j]}$ to $T_{I,m(j)}$ and
$w_{q,j}\in T_{J,[j]}$, it means that $w_{q,j}|_{\mathbb{R}^{k}/T_{m(j),[j]}}$
is indeed equal to $w_{q,j}|_{\mathbb{R}^{k}/T_{I,m(j)}}$ and orthogonal to
every vector in $T_{I,m(j)}$. Since $u_{p,i}|_{T_{[i],m(i)}}\in T_{I,[i]}$ and
$[i]\leq m(j)$, we have $\langle
u_{p,i}|_{T_{[i],m(i)}},w_{q,j}|_{\mathbb{R}^{k}/T_{m(j),[j]}}\rangle=0$ as
well. ∎

Now, the algorithm extends this alphabet set for each row and column so that
there exists a good solution from the alphabets that gives a good
approximation in half-clean hyperblocks as well. As dirty hyperblocks will be
very small compared to $OPT$ and can be totally ignored, this phase ensures
the existence of an overall good approximation solution from the alphabets. We
use the following result for the additive PTAS for Restricted $\ell_{0}$-Low
Rank Approximation. Recall that in this problem, in addition to
$A\in\mathbb{R}^{n_{R}\times n_{C}}$, we are additionally given a pair of
projection constraints, that is, matrices $P_{R}$ in $\mathbb{R}^{t_{R}\times
k}$ and $P_{C}$ in $\mathbb{R}^{t_{C}\times k}$ as well as real vectors
$(a_{p})_{p\in[n_{R}]}$ in $\mathbb{R}^{t_{R}}$ and $(b_{q})_{q\in[n_{C}]}$ in
$\mathbb{R}^{t_{c}}$, and we require that the matrices $U$ and $W$ also
satisfy $P_{R}(u_{p})=a_{p}$ and $P_{C}(w_{q})=b_{q}$ for all $p$ and $q$.

######  Proposition 4.3.

For any constants $\varepsilon>0$ and $k\in{\mathbb{N}}$, there exist
$t=2^{(1/\varepsilon)^{\mathrm{poly}(k)}}$,
$X=n^{(1/\varepsilon)^{\mathrm{poly}(k)}}$ and an algorithm running in time
$\mathrm{poly}(X)$ that performs the following task. Given an instance of
Restricted $\ell_{0}$-Low Rank Approximation consisting of
$A\in\mathbb{R}^{n_{R}\times n_{C}}$, $k\in{\mathbb{N}}$, and linear
constraints $P_{R}(u_{p})=a_{p}$ for each row $p\in[n_{R}]$ and
$P_{C}(w_{q})=b_{q}$ for each column $q\in[n_{C}]$, the algorithm outputs
$\Sigma_{p,x}\subseteq\mathbb{R}^{k}$ for each row $p\in[n_{R}]$, $x\in[X]$
and $\Sigma_{q,x}\subseteq\mathbb{R}^{k}$ for each column $q\in[n_{C}]$, $x\in
X$ such that

  1. (1)

every vector in $\Sigma_{p,x}$ satisfies the linear constraints for row $p$,

  2. (2)

every vector in $\Sigma_{q,x}$ satisfies the linear constraints for column
$q$, and

  3. (3)

$|\Sigma_{p,x}|,|\Sigma_{q,x}|\leq t$ for every $x\in[X]$.

For any $S_{R}\subseteq[n_{R}]$ and $S_{C}\subseteq[n_{C}]$, there exists
$x\in[X]$ and $u_{p}\in\Sigma_{p,x}$ for every row $p\in S_{R}$ and
$w_{q}\in\Sigma_{q,x}$ for every column $q\in S_{C}$ such that $|\\{(p,q)\in
S_{R}\times S_{C}:\langle u_{p},w_{q}\rangle\neq A_{p,q}\\}|\leq
OPT(A_{S_{R},S_{C}},k)+\varepsilon|S_{R}||S_{C}|$, where
$OPT(A_{S_{R},S_{C}},k)$ denotes the optimal value for Restricted
$\ell_{0}$-Low Rank Approximation restricted to the submatrix of $A$ induced
by $S_{R}\times S_{C}$ with the same linear constraints.

###### Proof.

It directly follows from Proposition 3.1, which shows the correctness of the
algorithm in Figure LABEL:A:mainalgo for Restricted $\ell_{0}$-Low Rank
Approximation. Here $X$ denotes the number of choices for the supercore,
determined by $R_{S},C_{S},E,M_{R_{S}},M_{C_{S}}$, and $t$ denotes the size of
the alphabet, determined by $\Phi\subseteq M_{R_{S}}\cup M_{C_{S}}$. ∎

Given this proposition, for each half-clean hyperblock
$\mathfrak{B}=\mathfrak{I}\times\mathfrak{J}$, choose an arbitrary
$i\in[\ell_{R}]$ and $j\in[\ell_{C}]$ such that $I_{i}\subseteq\mathfrak{I}$
and $J_{j}\subseteq\mathfrak{J}$, and run the above additive PTAS on the
matrix $A$ with $k\leftarrow k$, $\varepsilon\leftarrow\varepsilon_{2}$ where
each row $p$ has a constraint that its vector belongs to $T_{I,[i]}$ and its
projection to $T_{[i],m(i)}$ is $u_{p,i}$ (similarly for columns). For each
$p\in[n_{R}]$ and $x\in[X]$, it will create an alphabet set
$\Sigma_{p,i,x}\subseteq T_{I,[i]}$ For each $q\in[n_{C}]$, it will similarly
create an alphabet set $\Sigma_{q,j,x}\subseteq T_{J,[j]}$.

Recall that every row and column belongs to at most one half-dirty hyperblock.
Therefore, when we consider a solution where each row $p\in[n_{R}]$ with $p\in
I_{i}$ takes the vector guaranteed by the additive PTAS for the half-clean
hyperblock containing $I_{i}$ (or just $u_{p,i}$ if there is no such
hyperblock), and columns take analogous solutions, then the amount of errors
from the half-clean hyperblocks is at most $k\varepsilon_{2}$ times the size
of a half-clean hyperblock, which by Claim 2 is at most
$\frac{k\varepsilon_{2}}{\delta_{2}^{O(k^{2})}\varepsilon_{1}^{O(k)}}OPT$.
Note that By Claim 3, this solution extends the solution constructed in Phase
2 and still has the same guarantee in clean hyperblocks. By conservatively
ignoring all dirty hyperblocks which has an additional cost of
$\varepsilon_{1}k^{2}OPT$, The total error for this solution is at most

$OPT\bigg{(}1+\varepsilon_{0}/8+O\big{(}\frac{\tau}{\delta_{0}}+\frac{\delta_{2}}{\delta_{0}}\big{)}+\frac{k\varepsilon_{2}}{\delta_{2}^{O(k^{2})}\varepsilon_{1}^{O(k)}}+k^{2}\varepsilon_{1}\bigg{)}\bigg{(}1+4\delta_{1}\bigg{)}$

By ensuring that

$\bigg{(}1+\varepsilon_{0}/8+O\big{(}\frac{\tau}{\delta_{0}}+\frac{\delta_{2}}{\delta_{0}}\big{)}+\frac{k\varepsilon_{2}}{\delta_{2}^{O(k^{2})}\varepsilon_{1}^{O(k)}}+k^{2}\varepsilon_{1}\bigg{)}\bigg{(}1+4\delta_{1}\bigg{)}\leq
1+\varepsilon_{0},$ (5)

we get a $(1+\varepsilon_{0})$-approximation. To satisfy the dependencies
between parameters, we set the parameters as follows.

  * •

Parameters: $k$, $\varepsilon_{0}$, $\delta_{0}$ (layers), $\tau$ (goodness of
samples), $t_{0}$ (sample size), $\delta_{1}$ (failure probability),
$\varepsilon_{1}$ (clean/dirtiness of blocks), $\varepsilon_{2}$ (additive
PTAS guarantee), $\delta_{2}$ (super-separation).

  * •

(1): $\varepsilon_{1}k^{2}t_{0}^{2}\leq\delta_{1}/4$.

  * •

(2): $t_{0}\geq 2k^{2}\log(1/\delta_{1})/\delta_{0}$.

  * •

(3):
$t_{0}\geq\Omega\big{(}\frac{k}{\tau^{2}}\log(1/\tau)+\log(1/\delta_{1})\big{)}$.

  * •

$t_{0}\geq\mathrm{poly}(k/(\delta_{0}\varepsilon_{0}))$ to ensure that Lemma
4.2 works.

  * •

(4): $\delta_{2}<\varepsilon_{1}^{2}$.

  * •

(5):
$\bigg{(}1+\varepsilon_{0}/8+O\big{(}\frac{\tau}{\delta_{0}}+\frac{\delta_{2}}{\delta_{0}}\big{)}+\frac{k\varepsilon_{2}}{\delta_{2}^{O(k^{2})}\varepsilon_{1}^{O(k)}}+k^{2}\varepsilon_{1}\bigg{)}\bigg{(}1+4\delta_{1}\bigg{)}\leq
1+\varepsilon_{0}$,

  * •

Given $\varepsilon_{0}$ and $k$, fix $\delta_{0}=1/20k$,
$\delta_{1}=\varepsilon_{0}/100$, and $\tau=O(\varepsilon_{0}/\delta_{0})$ so
that the $O(\tau/\delta_{0})$ term in (5) is at most $\varepsilon_{0}/100$.

  * •

Choose $t_{0}=\mathrm{poly}(k/\varepsilon_{0})$ large enough to satisfy (2),
(3) and the condition of Lemma 4.2

  * •

Choose $\varepsilon_{1}=\mathrm{poly}(k/\varepsilon_{0})^{-1}$ small enough to
satisfy (1) and the $k^{2}/\varepsilon_{1}$ term in (5) is at most
$\varepsilon_{0}/100$.

  * •

Choose $\delta_{2}=\mathrm{poly}(k/\varepsilon_{0})^{-1}$ small enough to
satisfy (4) and the $O(\delta_{2}/\delta_{0})$ term in (5) is at most
$\varepsilon_{0}/100$.

  * •

Choose $\varepsilon_{2}=(2^{\mathrm{poly}(k/\varepsilon_{0})})^{-1}$ small
enough to satisfy (5).

##### Phase 4: Finishing off.

Let $\mathfrak{B}_{1},\dots,\mathfrak{B}_{\ell}$ be the half-clean hyperblocks
where we run the additive PTAS ($\ell\leq k$). Let
$(i_{1},j_{1}),\dots,(i_{\ell},j_{\ell})\in[\ell_{R}]\times[\ell_{C}]$ be the
representatives for those hyperblocks; for each $e\in[\ell]$,
$(i_{e},j_{e})\in\mathfrak{B}_{e}$ and we ran the additive PTAS after imposing
linear constraints according to $i_{e}$ and $j_{e}$. For $e\in[\ell]$, let
$x_{e}\in[X]$ be the good index guaranteed by Proposition 4.3 for
$\mathfrak{B}_{e}$. The correct $x_{1},\dots,x_{\ell}$ can be guessed from at
most $|X|^{k}$ choices.

Once the algorithm has the correct $x_{1},\dots,x_{\ell}$, it is guaranteed
that there is a constant-size alphabet set
$\Sigma_{p}:=\cup_{e\in[\ell]}\Sigma_{p,i_{e},x_{e}}\subseteq\mathbb{R}^{k}$
for each row $p\in[n_{R}]$ and
$\Sigma_{q}:=\cup_{e\in[\ell]}\Sigma_{q,j_{e},x_{e}}\subseteq\mathbb{R}^{k}$
for each column $q\in[n_{C}]$ such that there is a
$(1+\varepsilon_{0})$-approximate solution where each row and column gets its
vector from its alphabet set. Then the final phase of the algorithm is again
based on sampling; sample $s_{j,1},\dots,s_{j,t_{0}}$ from $J_{j}$ as usual,
and guess its correct vector from its alphabet set, and use them to vote for
the rows. The crucial difference is that, while we sample from $J_{j}$ that
relies on the layer structure, since we know that the guaranteed solution is
globally good, each row gets voted just once (as opposed to $\ell_{R}$ times
before) about its correct position in the entire space $\mathbb{R}^{k}$.
Formally, after guessing $\\{w_{s_{j,q}}\\}_{j\in[\ell_{C}],q\in[t_{0}]}$ from
the samples’ own alphabet sets, for each $p\in[n_{R}]$ we apply Lemma 4.2 with
$\varepsilon\leq\varepsilon_{0},\ell\leftarrow\ell_{C},N_{j}\leftarrow
J_{j},T_{j}\leftarrow
T_{j},\mathbb{R}^{k}\leftarrow\mathbb{R}^{k},u_{s_{j},q}\leftarrow
w_{s_{j},q}$. Then the lemma guarantees the expected value of the final
solution obtained is at most a factor $(1+\varepsilon_{0})$ worse than the
intended solution. (We do not need the first guarantee about the chosen vector
being equal to $x^{*}$. Also note that the vectors for rows might be outside
their alphabets.) Therefore, for some choice of samples and their positions
from their alphabets, the total error of the computed solution is at most
$(1+\varepsilon_{0})^{2}OPT$, finishing the proof of the theorem.

##### Total running time.

It can be checked that the the total number of guesses that Phase 1 and Phase
2 make is $n^{\mathrm{poly}(k/\varepsilon_{0})}$. Given our choice of
$\varepsilon_{2}=(2^{\mathrm{poly}(k/\varepsilon_{0})})^{-1}$, the total
running time spent on the additive PTASes is
$n^{(1/\varepsilon_{2})^{\mathrm{poly}(k)}}=n^{2^{\mathrm{poly}(k/\varepsilon_{0})}}$,
which is also an upper bound on $|X|$. The running time in Phase 4 is
dominated by the time to guess the correct $x_{1},\dots,x_{\ell}$, which is at
most $|X|^{k}\leq n^{2^{\mathrm{poly}(k/\varepsilon_{0})}}$. Therefore, the
total running time is at most $n^{2^{\mathrm{poly}(k/\varepsilon_{0})}}$.
After Phase 3, each vector in $\Sigma_{p}$ is described by the Thom encoding
with bit complexity at most $\mathrm{poly}_{k,\varepsilon}(\tau)$, where
$\tau$ is the bit complexity of the input matrix $A$, and the degree of the
polynomial is independent of $\varepsilon$ and $k$ . As mentioned in the
definition of $u_{p,i}$ before the statement of Lemma 4.2, the finally chosen
vector for each row and column will be the solution to a system of at most
$\mathrm{poly}(k)$ linear equations whose coefficients are from $\Sigma_{p}$
and $\Sigma_{q}$. Therefore, the final vectors can be computed using the real
algebraic solvers described in Section 2 and be described by Thom encodings
with bit complexity $\mathrm{poly}_{k,\varepsilon}(\tau)$, where the degree of
the polynomial is independent of $\varepsilon$ and $k$. ∎

###  4.1 Proof of Lemma 4.2

In this section, we prove Lemma 4.2, which is restated below.

See 4.2

###### Proof.

Let $S_{i}=\\{s_{i,1},\dots,s_{i,t}\\}$ be the set of samples from $N_{i}$.
For any $y\in\mathbb{R}^{k}$ and $i\in[\ell]$, let us define the following
three quantities.

  * •

$\alpha_{i}(y):=|\\{q\in N_{i}:\langle u_{q},y\rangle\neq\langle
u_{q},v\rangle\\}|$: the number of indices where $x^{*}$ and $y$ behave
differently.

  * •

$\beta_{i}(y):=|\\{q\in N_{i}:\langle u_{q},y\rangle\neq a_{q}\\}|$: the
number of errors when we choose $y$.

  * •

$\gamma_{i}(y):=|\\{q\in S_{i}:\langle u_{q},y\rangle\neq
a_{q}\\}|\cdot(n_{i}/t)$: the estimate of $\beta_{i}(y)$ using the samples
$s_{i,1},\dots,s_{i,t}$.

If $y$ is clear from context, let us just write
$\alpha_{i},\beta_{i},\gamma_{i}$, and let $\alpha,\beta,\gamma$ be the sum of
$\alpha_{i}$’s, $\beta_{i}$’s, $\gamma_{i}$’s respectively. And let
$\alpha^{*}_{i},\beta^{*}_{i},\gamma^{*}_{i}$ be the quantities when
$y=x^{*}$. Of course, we only see $\gamma_{i}(y)$.

For $y\in\mathbb{R}^{k}$ and $i\in[\ell]$, if $y-x^{*}$ is orthogonal to
$T_{i}$ (including the case $y=x^{*}$), say $y$ is fortunate in $i$. We have
$\langle y,u_{q}\rangle=\langle x^{*},u_{q}\rangle$ for every $q\in N_{i}$, so
$y$ and $x^{*}$ behave the same with respect to $N_{i}$. So,
$\alpha_{i}(y)=\alpha^{*}_{i},\beta_{i}(y)=\beta^{*}_{i},\gamma_{i}(y)=\gamma^{*}_{i}$.

When $y-x^{*}$ is not orthogonal to $T_{i}$, let $T_{y}$ be the proper
subspace of $T_{i}$ orthogonal to $y-x^{*}$, and $N_{y}\subseteq N_{i}$ be the
set of indices whose vectors are in $T_{y}$. Note that $\alpha_{i}^{*}=0$ by
definition, and $\alpha_{i}(y)=n_{i}-|N_{y}|$. If $i$ is the smallest index
such that $y-x^{*}$ is not orthogonal to $T_{i}$, the fullness of $T_{i}$
implies that $|N_{y}|\leq(1-\delta_{0})n_{i}$, which implies that
$\alpha_{i}(y)\geq\delta_{0}n_{i}$ and
$\beta_{i}(y)\geq\max(0,\alpha_{i}(y)-\beta_{i}^{*})$. (If
$|N_{y}|>(1-\delta_{0})n_{i}$ and $y-x^{*}$ is orthogonal to $T_{i-1}$, then
$T_{y}$ satisfies $T_{i-1}\subseteq T_{y}\subsetneq T_{i}$ and contains most
of $N_{i}$, which contradicts the fullness of $T_{i}$.)

For a set $E\subseteq N_{i}$, let $\gamma_{i}(E):=|E\cap
S_{i}|\cdot(n_{i}/t)$. Intuitively, $\gamma_{i}(E)$ is the estimate of $|E|$
via samples. If the samples are $\tau$-good, as $N_{y}$ is a subset of $N_{i}$
contained in a strict subspace of $T_{i}$,
$||N_{y}|-\gamma_{i}(N_{y})|\leq\tau|N_{i}|$. Let $W_{i}=\\{q\in N_{i}:\langle
v,u_{q}\rangle\neq a_{q}\\}$ be the set of indices where $x^{*}$ is wrong
(e.g., $|W_{i}|=q^{*}_{i}$). Now let $x\neq x^{*}$ be the chosen vector, which
means $\gamma(x)\leq\gamma^{*}$.

##### First claim.

We first prove the first claim, which shows that the conditional probability
of $x\neq x^{*}$ given the samples are $\tau$-good is at most
$O(\frac{OPT}{\delta_{0}n_{\ell}})$. If $\beta^{*}=OPT\geq
0.01\delta_{0}n_{\ell}$, the trivial probability bound of $1$ proves the
claim, so assume that $\beta^{*}<0.01\delta_{0}n_{\ell}$. The proof considers
the event that there exists $i\in[\ell]$ with
$\gamma_{i}(W_{i})>0.1\delta_{0}n_{i}$; we will show that this event will
happen with a small probability, and if it does not happen, our output $x$
must be equal to $x^{*}$.

######  Claim 4.

Suppose that $\gamma_{i}(W_{i})\leq 0.1\delta_{0}n_{i}$ for all $i\in[\ell]$.
Then $x=x^{*}$.

###### Proof.

Assume towards contradiction that $x\neq x^{*}$ and let $f$ be the first index
that $T_{f}$ is not orthogonal to $x-x^{*}$. As before, let $N_{x}=\\{q\in
N_{f}:\langle u_{q},x\rangle=\langle u_{q},x^{*}\rangle\\}$. Then the fullness
of $T_{f}$ ensures that $|N_{x}|\leq(1-\delta_{0})n_{f}$. Since the samples
are $\tau$-good, $\gamma_{f}(N_{f}\setminus
N_{x})\geq(\delta_{0}-\tau)n_{f}\geq 0.9\delta_{0}n_{f}$. Since we assume
$\gamma_{i}(W_{i})\leq 0.1\delta_{0}n_{i}$ for all $i$, then

$\sum_{i=f}^{\ell}\gamma_{i}(W_{i})\leq\sum_{i=f}^{\ell}0.1\delta_{0}n_{i}\leq
0.2\delta_{0}n_{f}$

is the estimated number errors $x^{*}$ makes in $N_{f},\dots,N_{\ell}$ and
while the estimated number of errors that $x$ makes in $N_{f}$ only is at
least

$\gamma_{f}((N_{f}\setminus N_{x})\setminus
W_{f})\geq\gamma_{f}(N_{f}\setminus N_{x})-\gamma_{f}(W_{f})\geq
0.9\delta_{0}n_{f}-0.1\delta_{0}n_{f}=0.8\delta_{0}n_{f},$

which leads to contradiction, because $x$ and $x^{*}$ get the same estimated
errors from $N_{1},\dots,N_{f-1}$. ∎

Finally, we bound the probability of having some $i\in[\ell]$ with
$\gamma_{i}(W_{i})>0.1\delta_{0}n_{i}$. Let $\zeta=OPT/n_{\ell}$, which
implies that $\zeta\geq OPT/n_{i}$ for all $i\in[\ell]$. Before the
conditioning, because samples were uniformly and independently sampled from
each $N_{i}$, Chernoff and union bounds imply that this probability is upper
bounded by

$\ell\bigg{(}\frac{e}{0.1\delta_{0}/\zeta}\bigg{)}^{0.1\delta_{0}t}.$

(When we sample from $N_{i}$, each sample from $i$ is from $W_{i}$ with
probability at most $\zeta$ and we bound the probability that the fraction of
the samples from $W_{i}$ is at least $0.1\delta_{0}$.) For some sufficiently
large $t=\Omega(\ell/\delta_{0})$, this probability is at most
$O(\zeta/\delta_{0})=O(OPT/(n_{\ell}\delta_{0}))$. Since we assumed that the
samples are $\tau$-good with probability at least $1/2$, the conditional
probability is at most $2$ times bigger than this.

##### Second claim.

For each $i\in[\ell]$ and $y\in\mathbb{R}^{k}$, let $W_{i,y}=\\{q\in
W_{i,y}:\langle y,u_{q}\rangle=a_{q}\\}$ be the set of indices where $x^{*}$
is wrong but $y$ is right. The VC dimension of the family $\\{W_{i,y}\\}_{y}$
for fixed $i$ is $O(k)$. If we define

$\tau^{\prime}_{i}:=\max\bigg{(}\max_{y}{\frac{||W_{i,y}|-\gamma_{i}(W_{i,y})|}{n_{i}}},\quad\frac{||W_{i}|-\gamma_{i}(W_{i})|}{n_{i}}\bigg{)},$

Then, for any $y\in\mathbb{R}^{k}$, since $\\{q\in N_{i}:\langle
y,u_{q}\rangle=a_{q}\\}=(N_{y}\setminus W_{i})\cup W_{i,y}$, we have
$|\beta_{i}(y)-\gamma_{i}(y)|\leq(\tau+2\tau^{\prime}_{i})n_{i}.$ Furthermore,
the standard sampling guarantee for sets systems with bounded VC dimension
[FM06] guarantees that, for a fixed
$t=\mathrm{poly}(k\ell/(\varepsilon\delta_{0}))$, $\tau^{\prime}_{i}$ is a
sub-gaussian random variable with the sub-gaussian norm
$\|\tau^{\prime}_{i}\|_{\psi_{2}}\leq\mathrm{poly}(\varepsilon\delta_{0}/(k\ell))$
[Ver18]. Therefore, if we let
$\tau^{\prime}:=\max_{i\in[\ell]}\tau_{i}^{\prime}$, one can ensure
$\mathbb{E}[\tau^{\prime}]\leq\varepsilon\delta_{0}/10000$.

Let $x$ be the chosen vector and $f$ be the first index that $T_{f}$ is not
orthogonal to $x-x^{*}$. Then $F:=\\{1,\dots,f-1\\}$ is the set of indices
where $x$ is fortunate. Let $X:=\beta(x)-\beta(x^{*})$ be the amount of
additional error we incur by choosing $x$. Note that $x$, $f$,
$\tau^{\prime}$, and $X$ are correlated random variables. We present the
following two ways to bound $X$ given $f$.

First method. The first method works well when $n_{f}$ is small compared to
$\beta^{*}$ (we will apply it when $\beta^{*}\geq 0.01\delta_{0}n_{f}$). Note
that $\gamma^{*}_{i}=\gamma_{i}$ when $i\in F$. For $i=f,\dots,\ell$, using
the approximation between $\beta$’s and $\gamma$’s when $i\notin F$, we have

$\sum_{i<f}\gamma^{*}_{i}+\sum_{i\geq f}(\beta_{i}-\tau
n_{i}-2\tau^{\prime}n_{i})\leq\gamma(x)\leq\gamma^{*}\leq\sum_{i<f}\gamma^{*}_{i}+\sum_{i\geq
f}(\beta_{i}^{*}+\tau n_{i}+2\tau^{\prime}n_{i}),$

which implies that the additional error caused by picking $x$ is at most

$(2\tau+4\tau^{\prime})\sum_{i\geq f}n_{i}\leq(4\tau+8\tau^{\prime})n_{f},$

using the fact that $n_{i}$’s are geometrically decreasing with a factor
$k\delta_{0}\leq 1/2$.

Second method. We will apply the second method when
$\beta^{*}<0.01\delta_{0}n_{f}$. In this case, we will conservatively say $x$
makes errors on all $N_{f},\dots,N_{\ell}$ so that $X\leq 2n_{f}$; what we
will do here is to bound the probability that $f$ takes such a value. Note
that $\beta_{f}+\beta^{*}_{f}\geq\delta_{0}n_{f}$ implies
$\beta_{f}>0.99\delta_{0}n_{f}$. We consider the following two events.

  * •

The probability of $\gamma_{f}(W_{f})>0.1\delta_{0}n_{f}$ is bounded by

$2\bigg{(}\frac{e}{(\delta_{0}/(10(\beta_{f}^{*}/n_{f})))}\bigg{)}^{(\delta_{0}/10)t}.$

(Before conditioning, each sample is from $W_{f}$ with probability
$\beta^{*}_{f}/n_{f}$, and we bound the probability that the fraction of the
samples from $W_{f}$ is at least $(\delta_{0}/10)$.) By letting
$t\geq\Omega(\ell/(\varepsilon\delta_{0}))$, we can ensure that the
probability is at most $(\beta^{*}/n_{f})\cdot(\varepsilon/80\ell)$.

  * •

If $\gamma_{f}(W_{f})\leq 0.1\delta_{0}n_{f}$, then the estimated errors of
$x$ from $N_{f}$ is already at least $0.5\delta_{0}n_{f}$. Because the total
number of entries from $N_{f+2},\dots,N_{\ell}$ is at most
$O((k\delta_{0})^{2}n_{f})$, so given that $\gamma_{f}(W_{f})\leq
0.1\delta_{0}n_{f}$, we should get
$\gamma_{f+1}(W_{f+1})\geq(\delta_{0}/3)n_{f}$ in order for $x^{*}$ to have
more estimated errors than $x$. If $n_{f+1}<(\delta_{0}/3)n_{f}$, this can
never happen. Otherwise, this probability is bounded by

$2\bigg{(}\frac{e}{(\delta_{0}/3)/(\beta_{f+1}^{*}/n_{f+1})}\bigg{)}^{(n_{f}/n_{f+1})(\delta_{0}/3)t}\leq
2\bigg{(}\frac{e}{(n_{f+1}/n_{f})(\delta_{0}/3)/(\beta^{*}/n_{f})}\bigg{)}^{(n_{f}/n_{f+1})(\delta_{0}/3)t}$

(Before conditioning, in $N_{f+1}$, each sample is from $W_{f+1}$ with
probability
$\beta^{*}_{f+1}/n_{f+1}\leq(\beta^{*}/n_{f})\cdot(n_{f}/n_{f+1})$, and we
bound the probability that the fraction of the samples from $W_{f+1}$ is at
least $(n_{f}/n_{f+1})(\delta_{0}/3)$.) Again, by letting
$t\geq\Omega(\ell/(\varepsilon\delta_{0}))$, one can again ensure that the
probability is at most $(\beta^{*}/n_{f})\cdot(\varepsilon/80\ell)$.

  * •

Therefore, when $i\in[\ell]$ is such that $\beta^{*}<0.01\delta_{0}n_{i}$, we
have $\Pr[f=i]\leq(\beta^{*}/n_{i})\cdot(\varepsilon/40\ell)$.

Finally, we use the above two methods to bound $\mathbb{E}[X]$. Let
$i^{\prime}$ be the first index that
$0.01\delta_{0}n_{i^{\prime}}\leq\beta^{*}$. The additional amount of error of
$x$ compared to $x^{*}$ (denoted by $X$) can be bounded by

$\displaystyle\sum_{i=i^{\prime}}^{\ell}\Pr[f=i]\mathbb{E}[X|f=i]+\sum_{i=1}^{i^{\prime}-1}\Pr[f=i]\mathbb{E}[X|f=i]$
$\displaystyle\leq$
$\displaystyle\sum_{i=i^{\prime}}^{\ell}\Pr[f=i]\mathbb{E}[(4\tau+8\tau^{\prime})n_{i}|f=i]+\sum_{i=1}^{i^{\prime}-1}(\beta^{*}/n_{i})(\varepsilon/40\ell)\cdot(2n_{i})$
$\displaystyle\leq$
$\displaystyle\sum_{i=i^{\prime}}^{\ell}n_{i^{\prime}}\Pr[f=i]\mathbb{E}[(4\tau+8\tau^{\prime})|f=i]+(\varepsilon/20)\beta^{*}$
$\displaystyle=$ $\displaystyle
n_{i^{\prime}}\cdot\mathbb{E}[(4\tau+8\tau^{\prime})|f\leq
i^{\prime}]\Pr[f\geq i^{\prime}]+(\varepsilon/20)\beta^{*}$
$\displaystyle\leq$ $\displaystyle
n_{i^{\prime}}\cdot\mathbb{E}[(4\tau+8\tau^{\prime})]+(\varepsilon/20)\beta^{*}$
$\displaystyle\leq$
$\displaystyle(200\beta^{*}/\delta_{0})(4\tau+\mathbb{E}[8\tau^{\prime}])+(\varepsilon/20)\beta^{*}\leq(1000\tau/\delta_{0}+0.1\varepsilon)\beta^{*}.$

∎

##  5 Hardness of $\ell_{0}$ Low-Rank Approximation

In this section, we give the $\Omega(\log n)$-factor hardness of
$\ell_{0}$-Low Rank Approximation.

See 1.3

Our reduction shall use the following well-known $\Omega(\log n)$-hardness of
Set Cover.

######  Theorem 5.1 ([Fei98],[DS14]).

Let $(U,\mathcal{S})$ be an instance of Set Cover with $|U|=n$. Then for
$\ell=\ell(n)$, it is NP-hard to distinguish between the following cases:

  * •

Yes Case. There exists a choice of
$S_{i_{1}},\ldots,S_{i_{\ell}}\in\mathcal{S}$ such that every element of $U$
is covered by exactly one of the sets.

  * •

No Case. Any set cover of $U$ by $\mathcal{S}$ is of size at least
$\Omega(\ell\cdot\log n)$.

###### Proof of Theorem 1.3.

Let ${\cal I}:=(U,\mathcal{S})$ with $|U|=n$ be an instance of Set Cover from
Theorem 1.3, and let $\ell=\ell(n)$ be as in the statement of the theorem.
Note that one can assume $m=\Omega(\ell\cdot\log n)$, because otherwise ${\cal
I}$ can never be a NO instance. We then construct our $\ell_{0}$-Low Rank
Approximation instance from ${\cal I}$ as follows.

##### Construction.

Given $\mathcal{S}:=\\{S_{1},\ldots,S_{m}\\}$, let $A\in\\{0,1\\}^{n\times m}$
be the matrix whose $i^{th}$ column is the indicator vector
$\mathbb{I}_{S_{i}}$ of the $i^{th}$ set. Let $V$ denote the kernel of $A$ and
let $b_{1},\ldots,b_{k}$ be any basis of $V$ (where $k$ is the dimension of
$V$). Without loss of generality, we may assume that there exists a vector $w$
such that $Aw=(-1,\ldots,-1)$ (otherwise the reduction can simply identify
this as a NO case instance). Then we construct our target matrix
$M\in\mathbb{R}^{m\times((m+1)k+1)}$ as follows.

  * •

The first $(m+1)k$ columns of $M$ consist of $(m+1)$-copies of
$b_{1},\ldots,b_{k}$.

  * •

The last column is the vector $w$.

The final instance consists of the matrix $M$, with rank parameter $k$, and
$\ell_{0}$ error parameter $\ell$. We now analyze the reduction.

##### Completeness.

Suppose ${\cal I}$ is a Yes instance. Then (up to re-ordering), we may assume
that the sets $S_{1},\ldots,S_{\ell}$ cover the all the elements, and every
element is covered exactly once. Let $v=-\sum_{i\in[\ell]}e_{i}$. Then
$Av=Aw=(-1,\ldots,-1)$ and hence $(w-v)\in V$. Then let
$M^{\prime}\in\mathbb{R}^{m\times((m+1)k+1)}$ be the matrix whose first
$(m+1)k$ columns are identical to that of $M$, and the last column is $w-v$.
Then clearly $M^{\prime}$ is of rank $k$ (since $b_{1},\dots,b_{k},w-v\in V$).
Furthermore, the two matrices only differ in the last column and hence
$\|M-M^{\prime}\|_{0}=\|v\|_{0}=\ell$.

##### Soundness.

Suppose ${\cal I}$ is a NO instance. We may assume that there exists a
rank-$k$ matrix $M^{\prime}\in\mathbb{R}^{m\times{(m+1)k+1}}$ such that
$\|M-M^{\prime}\|_{0}\leq m$ (otherwise we are done) – let $M^{\prime}$ denote
such a matrix with the smallest $\ell_{0}$-error. We have the following useful
claim:

######  Claim 5.

The column space of $M^{\prime}$ must be identical to $V$.

###### Proof.

Suppose not, then there exists $i\in[k]$ such that $b_{i}\notin{\rm
col}(M^{\prime})$ which implies that $\|M^{\prime}-M\|_{0}\geq m+1$ which
contradicts our choice of $M^{\prime}$. ∎

Now let us denote $\ell^{\prime}=\|M-M^{\prime}\|_{0}$, and let $v$ be the
last column of $M^{\prime}$. Then note that
$\|w-v\|_{0}\leq\|M-M^{\prime}\|_{0}=\ell^{\prime}$. Furthermore, using the
above claim we know that $v\in V$ and hence $A(w-v)=-(1,\ldots,1)$. But then
the non-zero indices of $(w-v)$ must form a valid set cover of $\mathcal{S}$,
which using the No case guarantee of ${\cal I}$ implies that
$\ell^{\prime}\geq\Omega(\ell\cdot\log n)$. ∎

## References

  * [ADLVKK03] Noga Alon, W. Fernandez De La Vega, Ravi Kannan, and Marek Karpinski.  Random sampling and approximation of MAX-CSPs.  Journal of Computer and System Sciences, 67(2):212–243, 2003.
  * [AKK95] Sanjeev Arora, David Karger, and Marek Karpinski.  Polynomial time approximation schemes for dense instances of NP-hard problems.  In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC), pages 284–293, 1995.
  * [BBB+19] Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, and David P. Woodruff.  A PTAS for $\ell_{p}$-low rank approximation.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 747–766. SIAM, 2019.
  * [BCW20] Ainesh Bakshi, Nadiia Chepurko, and David P. Woodruff.  Robust and sample optimal algorithms for PSD low rank approximation.  In IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 506–516. IEEE, 2020.
  * [BCW22] Ainesh Bakshi, Kenneth L Clarkson, and David P. Woodruff.  Low-rank approximation with $1/\epsilon^{3}$ matrix-vector products.  arXiv preprint arXiv:2202.05120, 2022.