Primal-dual interior point approach for computingl 1-solutions andl ∞-solutions of overdetermined linear systems

This paper concerns solving an overdetermined linear systemA ^T x=b in the leastl ₁-norm orl -norm sense, whereA ^m×n ,m<n. We show that the primal-dual interior point approach for linear programming can be applied, in an effective manner, to linear programming versions of thel ₁ andl -problems. The resulting algorithms are simple to implement and can attain quadratic or superlinear convergence rate. At each iteration, the algorithms must solve a linear system with anm×m positive-definite coefficient matrix of the formADA ^T , whereD is a positive diagonal matrix. The preliminary numerical results indicate that the proposed algorithms offer considerable promise.This research was supported in part by Grants NSF DMS-91-02761 and DOE DE-FG05-91-ER25100.     

Random walk on the infinite cluster of the percolation model

Summary We consider random walk on the infinite cluster of bond percolation on ^d . We show that, in the supercritical regime whend3, this random walk is a.s. transient. This conclusion is achieved by considering the infinite percolation cluster as a random electrical network in which each open edge has unit resistance. It is proved that the effective resistance of this network between a nominated point and the points at infinity is almost surely finite.G.R.G. acknowledges support from Cornell University, and also partial support by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell UniversityH.K. was supported in part by the N.S.F. through a grant to Cornell University