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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider the problem of matrix column subset selection, which selects asubset of columns from an input matrix such that the input can be wellapproximated by the span of the selected columns. Column subset selection hasbeen applied to numerous real-world data applications such as populationgenetics summarization, electronic circuits testing and recommendation systems.In many applications the complete data matrix is unavailable and one needs toselect representative columns by inspecting only a small portion of the inputmatrix. In this paper we propose the first provably correct column subsetselection algorithms for partially observed data matrices. Our proposedalgorithms exhibit different merits and limitations in terms of statisticalaccuracy, computational efficiency, sample complexity and sampling schemes,which provides a nice exploration of the tradeoff between these desiredproperties for column subset selection. The proposed methods employ the idea offeedback driven sampling and are inspired by several sampling schemespreviously introduced for low-rank matrix approximation tasks (Drineas et al.,2008; Frieze et al., 2004; Deshpande and Vempala, 2006; Krishnamurthy andSingh, 2014). Our analysis shows that, under the assumption that the input datamatrix has incoherent rows but possibly coherent columns, all algorithmsprovably converge to the best low-rank approximation of the original data asnumber of selected columns increases. Furthermore, two of the proposedalgorithms enjoy a relative error bound, which is preferred for column subsetselection and matrix approximation purposes. We also demonstrate through boththeoretical and empirical analysis the power of feedback driven samplingcompared to uniform random sampling on input matrices with highly correlatedcolumns.

Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data