Arvind K. Saibaba

Ilse C. F. Ipsen, Arvind K. Saibaba

The problem is to select k columns with maximal volume from a real mxn matrix X. We show that the logarithm of the volume is a submodular function on columns of X, and for full column-rank matrices X with sufficiently large singular values, it is a non-negative non-decreasing function. As a consequence, traditional Businger-Golub QR with column pivoting is a greedy algorithm, with a relative error of at most 37 percent. In contrast, Gu-Eisenstat strong rank-revealing QR is a 1-interchange algorithm, with a relative error of at most 50 percent. The higher accuracy, under this metric, of the simple QR with column pivoting confirms its well known effectiveness in practice. For general matrices, we show that Businger-Golub QR is a greedy algorithm, and Gu-Eisenstat QR a 1-interchange algorithm for maximizing the trace of the upper triangular matrix in a QR factorization of X, with Businger-Golub again having a better error bound. This is extended to finding kxk submatrices of maximal volume in symmetric positive-definite matrices.

Elle Buser, Julianne Chung, Hugo Díaz et al.

We consider inverse problems with linear forward models and Gaussian priors, but with unknown hyperparameters that may arise from the model, the noise, or the specification of the prior. We model this using a hierarchical Bayes framework resulting in a posterior distribution that is non-Gaussian, in general, and challenging to sample from. Consequently, we use an empirical Bayes framework for estimating the maximum a posteriori estimate of the hyperpameters by considering the marginalized posterior distribution. However, the optimization problem is also computationally challenging due to the need for repeated evaluation of log determinants. To address this issue, we propose a Majorization-Minimization with Monte Carlo approach, which we call M$^{3}$C, for hyperparameter estimation. Specifically, we replace the challenging optimization problem with a sequence of simpler ones by utilizing a majorization function (or majorant) for the log-determinant term, combined with a Monte Carlo estimator to approximate the majorant. We provide theoretical results, showing that under certain assumptions, the M$^{3}$C iterates converge with high probability to a critical point of the original cost function. A variety of numerical examples are provided from seismic tomography, super-resolution imaging, and contaminant source identification.