Optimization meets Statistics: Fast global convergence for high-dimensional statistical recovery
Abstract
Many methods for solving high-dimensional statistical inverse problems are based on convex optimization problems formed by the weighted sum of a loss function with a norm-based regularizer.
\\
Particular examples include $\ell_1$-based methods for sparse vectors and matrices, nuclear norm for low-rank matrices, and various combinations thereof for matrix decomposition and robust PCA. In this talk, we describe an interesting connection between computational and statistical efficiency, in particular showing that the same conditions that guarantee that an estimator has good statistical error can also be used to certify fast convergence of first-order optimization methods up to statistical precision.
\\
\\
Joint work with Alekh Agarwahl and Sahand Negahban Pre-print (to appear in Annals of Statistics)
\\
http://www.eecs.berkeley.edu/~wainwrig/Papers/AgaNegWai12b_SparseOptFul…
Computed tomography for X-rays: old 2-D results, relevance to new 3-D spiral CT problems
Real symmetric matrices with multiple eigenvalues
Abstract
We describe "avoidance of crossing" and its explanation by von
Neumann and Wigner. We show Lax's criterion for degeneracy and then
discover matrices whose determinants give the discriminant of the
given matrix. This yields a simple proof of the bound given by
Ilyushechkin on the number of terms in the expansion of the discriminant
as a sum of squares. We discuss the 3 x 3 case in detail.
How to approach non-normal matrix eigenvalue problems
Abstract
Non-normal matrices can be tiresome; some eigenvalues may be phlegmatic while others may be volatile. Computable error bounds are rarely used in such computations. We offer a way to proceed. Let (e,q,p') be an approximate eigentriple for non-normal B. Form column and row residuals r = Bq - qe and s' = p'B - ep'. We establish the relation between the smallest perturbation E, in both spectral and Frobenius norms, that makes the approximations correct and the norms of r and s'. Our results extend to the case when q and p are tall thin matrices and e is a small square matrix. Now regard B as a perturbation of B-E to obtain a (first order) bound on the error in e as a product of ||E|| and the condition number of e, namely (||q|| ||p'||)/|p'q|.
(a) Another Orthogonal Matrix & (b) An application of Pfaff's Theorem (on skew-symmetric matrices)
Abstract
Abstract 1 Another Orthogonal Matrix
A householder reflection and a suitable product of Givens rotations are two well known examples of an
orthogonal matrix with given first column. We present another way to produce such a matrix and apply
it to produce a "fast Givens" method to compute the R factor of A, A = QR. This approach avoids the danger
of under/overflow.
(joint work with Eric Barszcz)
Abstract 2 An application of Pfaff's Theorem (on skew-symmetric matrices)
There are no constraints on the eigenvalues of a product of two real symmetric matrices but what about the
product of two real skew-symmetric matrices?
(joint work with A Dubrulle)
The Envelope Method
Abstract
The task is to compute orthogonal eigenvectors (without Gram-Schmidt) of symmetric tridiagonals for isolated clusters of close eigenvalues. We review an "old" method, the Submatrix method, and describe an extension which significantly enlarges the scope to include several mini-clusters within the given cluster. An essential feature is to find the envelope of the associated invariant subspace.
14:00
1st - A nonlinear Krylov accelerator for Modified Newton; 2nd - 3D computerized tomography from 4D data
Abstract
First, I'll give a very brief update on our nonlinear Krylov accelerator for the usual Modified Newton's method. This simple accelerator, which I devised and Neil Carlson implemented as a simple two page Fortran add-on to our implicit stiff ODEs solver, has been robust, simple, cheap, and automatic on all our moving node computations since 1990. I publicize further experience with it here, by us and by others in diverse fields, because it is proving to be of great general usefulness, especially for solving nonlinear evolutionary PDEs or a smooth succession of steady states.
Second, I'll report on some recent work in computerized tomography from X-rays. With colored computer graphics I'll explain how the standard "filtered backprojection" method works for the classical 2D parallel beam problem. Then with that backprojection kernel function H(t) we'll use an integral "change of variables" approach for the 2D fan-beam geometry. Finally, we turn to the tomographic reconstruction of a 3D object f(x,y,z) from a wrapped around cylindical 2D array of detectors opposite a 2D array of sources, such as occurs in PET (positron-emission tomography) or in very-wide-cone-beam tomography with a finely spaced source spiral.