English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the Low Rank Approximation problem, where the input consists of amatrix $A \in \mathbb{R}^{n_R \times n_C}$ and an integer $k$, and the goal isto find a matrix $B$ of rank at most $k$ that minimizes $\| A - B \|_0$, whichis 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 improvesthe previous best $poly(k)$-approximation.  Our algorithm is obtained by viewing the problem as a Constraint SatisfactionProblem (CSP) where each row and column becomes a variable that can have avalue from $\mathbb{R}^k$. In this view, we have a constraint between each rowand column, which results in a {\em dense} CSP, a well-studied topic inapproximation algorithms. While most of previous algorithms focus onfinite-size (or constant-size) domains and involve an exhaustive enumerationover the entire domain, we present a new framework that bypasses such anenumeration in $\mathbb{R}^k$. We also use tools from the rich literature ofLow Rank Approximation in different objectives (e.g., $\ell_p$ with $p \in (0,\infty)$) or domains (e.g., finite fields/generalized Boolean). We believe thatour techniques might be useful to study other real-valued CSPs and matrixoptimization problems.  On the hardness side, when $k$ is part of the input, we prove that Low RankApproximation 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 SetExpansion Hypothesis).

A PTAS for $\ell_0$-Low Rank Approximation: Solving Dense CSPs over Reals