MSTuE41
Numerical Linear Algebra Techniques in Massive Data Analysis
Date: August 11
Time: 16:0018:10
Room: 303B
(Note: Click title to show the abstract.)
Organizer:
Gu, Ming (Univ. of California Berkeley)
Abstract: Effective and efficient treatment of massive data sets has become increasing
important in this age of information explosion. Most machine learning and data analysis algorithms for massive data sets require huge amounts of computational time.
In this minisymposium, we discuss effective algorithms for analyzing massive data sets
by exploiting efficient numerical linear algebra techniques.
This minisymposium is sponsored by the SIAG.
MSTuE411
16:0016:30
Efficient Algorithms for Solving KadisonSinger Problems
Gu, Ming (Univ. of California Berkeley)
Abstract: The KadisonSinger Problems are a large class of related problems in a dozen areas of research in pure mathematics, applied mathematics and Engineering. Recent work of
Marcus, Spielman and Srivastava shows the existence of the solutions to these problems. In this talk, we present efficient algorithms for solving these problems, including algorithms for computing the Weaver and Feichtinger partitions.
MSTuE412
16:3017:00
A Dynamic Approach to Sparse Recovery
Yao, Yuan (Peking Univ.)
Abstract: We propose a dynamic approach to sparse recovery under noisy linear measurements, which solve a dilemma in statistics discovered by Fan and Li in 2001: LASSO is biased and to remove the bias while keeping sparse recovery, nonconvex regularization is necessary. However, we will show that a simple dynamics, based on gradient flow in dual space, will generate unbiased and signconsistent solution without boiling to nonconvex optimization.
MSTuE413
17:0017:30
Fast randomized iteration for matrix inversion, eigenproblems, and exponentiation
Lim, LekHeng (Univ. of Chicago)
Weare, Jonathan (Univ. of Chicago)
Abstract: We introduce randomized iterative algorithms inspired by the diffusion Monte Carlo algorithm for some common tasks in numerical linear algebra. These algorithms work in either linear or constant cost per iteration. Traditional iterative methods in numerical linear algebra were created in part to deal with instances where a matrix (of size O(n^2)) is too big to store. Our O(1) iterative methods address instances where even a vector (of size O(n)) is too big to store.
CPTuE414
17:3017:50
The lowrank basis problem for a matrix subspace
Uschmajew, Andre (Univ. of Bonn)
Nakatsukasa, Yuji (Univ. of Tokyo)
Soma, Tasuku (Univ. of Tokyo)
Abstract: Given a matrix subspace, there are relevant reasons to ask for a basis of lowest rank. A greedy algorithm will provably find it, but the subproblems are NPhard. We propose an algorithm with two phases: first, basis ranks are estimated using soft singular value thresholding. Second, a basis is constructed using hard thresholding and subspace projection. Alternatively, when the basis consists of rankone matrices, one may find it using tensor decomposition.
CPTuE415
17:5018:10
Simultaneous reduction of large sparse matrix pencils
Sidje, Roger (Univ. of Alabama)
Abstract: There are algorithms to simultaneously reduce a pair of symmetric matrices to tridiagonaltridiagonal form with a congruent transformation, but these algorithms are impractical for large sparse matrices because they successively update the matrices and so destroy their sparsity.
We consider pairs that are either symmetric or nonsymmetric in this work. We describe a new Krylov subspace projection method to reduce a symmetric pair to tridiagonaltriadiagonal form with a threeterm recurrence that can be interrupted midstream in a Lanczoslike manner.
We generalize to reduce a nonsymmetric pair to HessenbergHessenberg form in an Arnoldilike manner. While the new methods also involve shiftandinvert operations as previous algorithms do, the sparse context means that this step can itself be handled with other specialized methods meant for sparse linear systems. Applications of this work include areas such as the generalized eigenvalue problem where partial simultaneous projection methods can be applied to the matrix pencil.
Return
Footnote: Code: TypeDateTimeRoom No.
Type : IL=Invited Lecture, SL=Special Lectures, MS=Minisymposia, IM=Industrial Minisymposia, CP=Contributed Papers, PP=Posters
Date: Mo=Monday, Tu=Tuesday, We=Wednesday, Th=Thursday, Fr=Friday
Time : A=8:309:30, B=10:0011:00, C=11:1012:10, BC=10:0012:10, D=13:3015:30, E=16:0018:00, F=19:0020:00, G=12:1013:30, H=15:3016:00
Room No.: TBA
