Thu, 21 Feb 2013

14:00 - 15:00
Gibson Grd floor SR

Optimization meets Statistics: Fast global convergence for high-dimensional statistical recovery

Professor Martin Wainwright
(UC Berkeley)
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…

Thu, 10 Oct 2002

14:00 - 15:00
Comlab

Real symmetric matrices with multiple eigenvalues

Prof Beresford Parlett
(UC Berkeley)
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.

Thu, 27 Apr 2006

14:00 - 15:00
Comlab

How to approach non-normal matrix eigenvalue problems

Prof Beresford Parlett
(UC Berkeley)
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|.

Thu, 28 Apr 2005

14:00 - 15:00
Comlab

(a) Another Orthogonal Matrix & (b) An application of Pfaff's Theorem (on skew-symmetric matrices)

Prof Beresford Parlett
(UC Berkeley)
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)

Thu, 08 May 2008

14:00 - 15:00
Comlab

The Envelope Method

Prof Beresford Parlett
(UC Berkeley)
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.

Thu, 02 Jun 2005
14:00
Comlab

1st - A nonlinear Krylov accelerator for Modified Newton; 2nd - 3D computerized tomography from 4D data

Professor Keith Miller
(UC Berkeley)
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.

Subscribe to UC Berkeley