2018/11/04 by Song, Zhao, Woodruff, David P., Zhong, Peilin · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.1811.01442
There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank-k matrix B minimizing the sum of absolute values of differences to a given n-by-n matrix A, min_\textrmrank-k~B‖A-B‖1, or more generally finding a rank-k matrix B which minimizes the sum of p-th powers of absolute values of differences, min_\textrmrank-k~B‖A-B‖pp. Many of these algorithms are linear time columns subset selection algorithms, returning a subset of poly(k log n) columns whose cost is no more than a poly(k) factor larger than the cost of the best rank-k matrix. The above error measures are special cases of the following general entrywise low rank approximation problem: given an arbitrary function g:ℝ → ℝ≥ 0, find a rank-k matrix B which minimizes ‖A-B‖g = ∑i,jg(Ai,j-Bi,j). A natural question is which functions g admit efficient approximation algorithms? Indeed, this is a central question of recent work studying generalized low rank models. In this work we give approximation algorithms for every function g which is approximately monotone and satisfies an approximate triangle inequality, and we show both of these conditions are necessary. Further, our algorithm is efficient if the function g admits an efficient approximate regression algorithm. Our approximation algorithms handle functions which are not even scale-invariant, such as the Huber loss function, which we show have very different structural properties than ℓp-norms, e.g., one can show the lack of scale-invariance causes any column subset selection algorithm to provably require a √(log n) factor larger number of columns than ℓp-norms; nevertheless we design the first efficient column subset selection algorithms for such error measures.