The discrete empirical interpolation method (DEIM) may be used as an index selection strategy for formulating a CUR factorization. A notable drawback of the original DEIM algorithm is that the number of column or row indices that can be selected is limited to the number of input singular vectors. We propose a new variant of DEIM, which we call L-DEIM, a combination of the strength of deterministic leverage scores and DEIM. This method allows for the selection of a number of indices greater than the number of available singular vectors. Since DEIM requires singular vectors as input matrices, L-DEIM is particularly attractive for example in big data problems when computing a rank-$k$-SVD approximation is expensive even for moderately small $k$ since it uses a lower-rank SVD approximation instead of the full rank-$k$ SVD. We empirically demonstrate the performance of L-DEIM, which despite its efficiency, may achieve comparable results to the original DEIM and even better approximations than some state-of-the-art methods.
翻译:独立的实证内插法(DEIM)可以作为一种指数选择战略用于制定 CUR 要素化。最初的 DEIM 算法的一个显著缺点是,可以选择的列或行指数数量限于输入单矢量的数量。我们提出了一个新的DEIM变量,我们称之为L-DEIM,这是确定性杠杆分数和DEIM的结合。这种方法允许选择比现有单矢量更多的一些指数。由于DEIM 需要单矢量作为输入矩阵,L-DEIM 在计算一等-k$-SVD近似值时,对于大数据问题特别有吸引力,即使是对于中小的量的量的量,因为它使用低层次的SVD近似值而不是整级-k$SVD。我们从经验上证明了L-DEIM的性能,尽管其效率可能达到与原始的DEIM的类似结果,甚至比一些最先进的方法要好。