In today's information systems, the availability of massive amounts of data necessitates the development of fast and accurate algorithms to summarize these data and represent them in a succinct format. One crucial problem in big data analytics is the selection of representative instances from large and massively-distributed data, which is formally known as the Column Subset Selection (CSS) problem. The solution to this problem enables data analysts to understand the insights of the data and explore its hidden structure. The selected instances can also be used for data preprocessing tasks such as learning a low-dimensional embedding of the data points or computing a low-rank approximation of the corresponding matrix. This paper presents a fast and accurate greedy algorithm for large-scale column subset selection. The algorithm minimizes an objective function which measures the reconstruction error of the data matrix based on the subset of selected columns. The paper first presents a centralized greedy algorithm for column subset selection which depends on a novel recursive formula for calculating the reconstruction error of the data matrix. The paper then presents a MapReduce algorithm which selects a few representative columns from a matrix whose columns are massively distributed across several commodity machines. The algorithm first learns a concise representation of all columns using random projection, and it then solves a generalized column subset selection problem at each machine in which a subset of columns are selected from the sub-matrix on that machine such that the reconstruction error of the concise representation is minimized. The paper demonstrates the effectiveness and efficiency of the proposed algorithm through an empirical evaluation on benchmark data sets.
In the area of numerical linear algebra, the column pivoting method exploited by the QR decomposition @cite_32 permutes the columns of the matrix based on their norms to enhance the numerical stability of the QR decomposition algorithm. The first @math columns of the permuted matrix can be directly selected as representative columns. The Rank-Revealing QR (RRQR) decomposition @cite_28 @cite_15 @cite_44 @cite_16 is a category of QR decomposition methods which permute columns of the data matrix while imposing additional constraints on the singular values of the two sub-matrices of the upper-triangular matrix @math corresponding to the selected and non-selected columns. It has been shown that the constrains on the singular values can be used to derive an theoretical guarantee for the column-based reconstruction error according to spectral norm @cite_12 .
@cite_28 @cite_32 @cite_44 @cite_15 @cite_16 @cite_12
2007266146 2008205484 2021604182 2093010960
We develop algorithms and implementations for computing rank-revealing QR (RRQR) factorizations of dense matrices. First, we develop an efficient block algorithm for approximating an RRQR factorization, employing a windowed version of the commonly used Golub pivoting strategy, aided by incremental condition estimation. Second, we develop efficiently implementable variants of guaranteed reliable RRQR algorithms for triangular matrices originally suggested by Chandrasekaran and Ipsen and by Pan and Tang. We suggest algorithmic improvements with respect to condition estimation, termination criteria, and Givens updating. By combining the block algorithm with one of the triangular postprocessing steps, we arrive at an efficient and reliable algorithm for computing an RRQR factorization of a dense matrix. Experimental results on IBM RS 6000 SGI R8000 platforms show that this approach performs up to three times faster that the less reliable QR factorization with column pivoting as it is currently implemented in LAPACK, and comes within 15 of the performance of the LAPACK block algorithm for computing a QR factorization without any column exchanges. Thus, we expect this routine to be useful in may circumstances where numerical rank deficiency cannot be ruled out, but currently has been ignored because of the computational cost of dealing with it. Abstract : An algorithm is presented for computing a column permutation Pi and a QR-factorization (A)(Pi) = QR of an m by n (m or = n) matrix A such that a possible rank deficiency of A will be revealed in the triangular factor R having a small lower right block. For low rank deficient matrices, the algorithm is guaranteed to reveal the rank of A and the cost is only slightly more than the cost of one regular QR-factorization. A posteriori upper and lower bounds on the singular values of A are derived and can be used to infer the numerical rank of A. Keywords: QR-Factorization; Rank deficient matrices; Least squares computation; Subset selection; Rank; Singular values. Abstract By exploring properties of Schur complements, this paper presents bounds on the existence of rank-revealing LU factorizations that are comparable with those of rank-revealing QR factorizations. The new bounds provide substantial improvement over previously derived bounds. This paper also proposes two algorithms using Gaussian elimination with a “block pivoting” strategy to select a subset of columns from a given matrix which has a guaranteed relatively large smallest singular value. Each of these two algorithms is faster than its orthogonal counterpart for dense matrices. If implemented appropriately, these algorithms are faster than the corresponding rank-revealing QR methods, even when the orthogonal matrices are not explicitly updated. Based on these two algorithms, an algorithm using only Gaussian elimination for computing rank-revealing LU factorizations is introduced. Motivated by the enormous amounts of data collected in a large IT service provider organization, this paper presents a method for quickly and automatically summarizing and extracting meaningful insights from the data. Termed Clustered Subset Selection (CSS), our method enables program-guided data explorations of high-dimensional data matrices. CSS combines clustering and subset selection into a coherent and intuitive method for data analysis. In addition to a general framework, we introduce a family of CSS algorithms with different clustering components such as k-means and Close-to-Rank-One (CRO) clustering, and Subset Selection components such as best rank-one approximation and Rank-Revealing QR (RRQR) decomposition. From an empirical perspective, we illustrate that CSS is achieving significant improvements over existing Subset Selection methods in terms of approximation errors. Compared to existing Subset Selection techniques, CSS is also able to provide additional insight about clusters and cluster representatives. Finally, we present a case-study of program-guided data explorations using CSS on a large amount of IT service delivery data collection.