题目：Least Squares Approximation via Sparse Subsampled Randomized Hadamard Transform
时间：2020年6月12日（周五）16:00-17:00
地点：腾讯会议
摘要：Solving least squares (LS) problems is a major topic in many applications. With recent data explosion, traditional approach is no longer suitable while working with large datasets, instead, randomized algorithms become popular in addressing this issue. In this talk we introduce a new randomized algorithm - sparse subsampled randomized Hadamard transform (SpSRHT) for solving overdetermined least squares problems. Its unique block structure connects two most commonly used randomized algorithms subsampled randomized Hadamard transform (SRHT) and sparse subspace embedding (SpEmb) and creates a general framework which contains them as special cases. We show theoretically that SpSRHT with different parameters reaches the relative-error bound with sketch size ranging from the sketch size required by SpEmb to SRHT. The new algorithm closes the gap between SRHT and SpEmb which provides the possibility of balancing accuracy and efficiency demonstrated in them. This advantage of SpSRHT is also well illustrated in our numerical experiments.