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/

Zendy Plus

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

Zendy Tools

Zendy Open

We consider the problem of linear regression where the $\ell_2^n$ norm loss(i.e., the usual least squares loss) is replaced by the $\ell_p^n$ norm. Weshow how to solve such problems up to machine precision in $O^*(n^{|1/2 -1/p|})$ (dense) matrix-vector products and $O^*(1)$ matrix inversions, oralternatively in $O^*(n^{|1/2 - 1/p|})$ calls to a (sparse) linear systemsolver. This improves the state of the art for any $p\not\in \{1,2,+\infty\}$.Furthermore we also propose a randomized algorithm solving such problems in{\em input sparsity time}, i.e., $O^*(Z + \mathrm{poly}(d))$ where $Z$ is thesize of the input and $d$ is the number of variables. Such a result was onlyknown for $p=2$. Finally we prove that these results lie outside the scope ofthe Nesterov-Nemirovski's theory of interior point methods by showing that anysymmetric self-concordant barrier on the $\ell_p^n$ unit ball hasself-concordance parameter $\tilde{\Omega}(n)$.

An homotopy method for $\ell_p$ regression provably beyond self-concordance and in input-sparsity time