MATRIX PROBING AND ITS CONDITIONING

作者：Chiu Jiawei^*; Demanet Laurent

来源：SIAM Journal on Numerical Analysis, 2012, 50(1): 171-193.

DOI：10.1137/110825972

• randomized algorithms
• pseudodifferential operators
• preconditioners
• conditioning
• system identification
• large deviation estimates

When a matrix A with n columns is known to be well-approximated by a linear combination of basis matrices B-1, ... , B-p, we can apply A to a random vector and solve a linear system to recover this linear combination. The same technique can be used to obtain an approximation to A(-1). A basic question is whether this linear system is well-conditioned. This is important for two reasons: a well-conditioned system means (1) we can invert it and (2) the error in the reconstruction can be controlled. In this paper, we show that if the Gram matrix of the B-j's is sufficiently well-conditioned and each B-j has a high numerical rank, then n alpha p log(2) n will ensure that the linear system is well-conditioned with high probability. Our main application is probing linear operators with smooth pseudodifferential symbols such as the wave equation Hessian in seismic imaging [L. Demanet et al., Appl. Comput. Harmonic Anal., 32 (2012), pp. 155-168]. We also demonstrate numerically that matrix probing can produce good preconditioners for inverting elliptic operators in variable media.

• 出版日期2012