Generalized Low-Rank Approximations

We study the frequent problem of approximating a target matrix with a matrix of lower rank. We provide a simple and efficient (EM) algorithm for solving {\\em weighted} low rank approximation problems, which, unlike simple matrix factorization problems, do not admit a closed form solution in general. We analyze, in addition, the nature of locally optimal solutions that arise in this context, demonstrate the utility of accommodating the weights in reconstructing the underlying low rank representation, and extend the formulation to non-Gaussian noise models such as classification (collaborative filtering).

Optimal Approximations of the Frequency Moments

We give a one-pass, O~(m^{1-2/k})-space algorithm for estimating the k-th frequency moment of a data stream for any real k>2. Together with known lower bounds, this resolves the main problem left open by Alon, Matias, Szegedy, STOC'96. Our algorithm enables deletions as well as insertions of stream elements.

Automatic Qualitative Analysis of Ordinary Differential Equations Using Piecewise Linear Approximations

This paper explores automating the qualitative analysis of physical systems. It describes a program, called PLR, that takes parameterized ordinary differential equations as input and produces a qualitative description of the solutions for all initial values. PLR approximates intractable nonlinear systems with piecewise linear ones, analyzes the approximations, and draws conclusions about the original systems. It chooses approximations that are accurate enough to reproduce the essential properties of their nonlinear prototypes, yet simple enough to be analyzed completely and efficiently. It derives additional properties, such as boundedness or periodicity, by theoretical methods. I demonstrate PLR on several common nonlinear systems and on published examples from mechanical engineering.

Structural manifestation of the delocalization error of density functional approximations: C(4N+2) rings and C(20) bowl, cage, and ring isomers.

The ground state structure of C(4N+2) rings is believed to exhibit a geometric transition from angle alternation (N < or = 2) to bond alternation (N > 2). All previous density functional theory (DFT) studies on these molecules have failed to reproduce this behavior by predicting either that the transition occurs at too large a ring size, or that the transition leads to a higher symmetry cumulene. Employing the recently proposed perspective of delocalization error within DFT we rationalize this failure of common density functional approximations (DFAs) and present calculations with the rCAM-B3LYP exchange-correlation functional that show an angle-to-bond-alternation transition between C(10) and C(14). The behavior exemplified here manifests itself more generally as the well known tendency of DFAs to bias toward delocalized electron distributions as favored by Huckel aromaticity, of which the C(4N+2) rings provide a quintessential example. Additional examples are the relative energies of the C(20) bowl, cage, and ring isomers; we show that the results from functionals with minimal delocalization error are in good agreement with CCSD(T) results, in contrast to other commonly used DFAs. An unbiased DFT treatment of electron delocalization is a key for reliable prediction of relative stability and hence the structures of complex molecules where many structure stabilization mechanisms exist.

Macroscopic limit of time-dependent density-functional theory for adiabatic local approximations of the exchange-correlation kernel

Time-dependent density-functional theory is a rather accurate and efficient way to compute electronic excitations for finite systems. However, in the macroscopic limit (systems of increasing size), for the usual adiabatic random-phase, local-density, or generalized-gradient approximations, one recovers the Kohn-Sham independent-particle picture, and thus the incorrect band gap. To clarify this trend, we investigate the macroscopic limit of the exchange-correlation kernel in such approximations by means of an algebraical analysis complemented with numerical studies of a one-dimensional tight-binding model. We link the failure to shift the Kohn-Sham spectrum of these approximate kernels to the fact that the corresponding operators in the transition space act only on a finite subspace.

Improved description of chemical barriers with generalized gradient approximations (GGAs) and meta-GGAs

The performance of exchange and correlation (xc) functionals of the generalized gradient approximation (GGA) type and of the meta-GGA type in the calculation of chemical reactions is related to topological features of the electron density which, in turn, are connected to the orbital structure of chemical bonds within the Kohn-Sham (KS) theory. Seventeen GGA and meta-GGA xc functionals are assessed for 15 hydrogen abstraction reactions and 3 symmetrical S(N)2 reactions. Systems that are problematic for standard GGAs characteristically have enhanced values of the dimensionless gradient argument s(sigma)(2) with local maxima in the bonding region. The origin of this topological feature is the occupation of valence KS orbitals with an antibonding or essentially nonbonding character. The local enhancement of s(sigma)(2) yields too negative exchange-correlation energies with standard GGAs for the transition state of the S(N)2 reaction, which leads to the reduced calculated reaction barriers. The unwarranted localization of the effective xc hole of the standard GGAs, i.e., the nondynamical correlation that is built into them but is spurious in this case, wields its effect by their s(sigma)(2) dependence. Barriers are improved for xc functionals with the exchange functional OPTX as x component, which has a modified dependence on s(sigma)(2). Standard GGAs also underestimate the barriers for the hydrogen abstraction reactions. In this case the barriers are improved by correlation functionals, such as the Laplacian-dependent (LAP3) functional, which has a modified dependence on the Coulomb correlation of the opposite- and like-spin electrons. The best overall performance is established for the combination OLAP3 of OPTX and LAP3.

On the required shape corrections to the local density and generalized gradient approximations to the Kohn-Sham potentials for molecular response calculations of (hyper)polarizabilities and excitation energies

It is well known that shape corrections have to be applied to the local-density (LDA) and generalized gradient (GGA) approximations to the Kohn-Sham exchange-correlation potential in order to obtain reliable response properties in time dependent density functional theory calculations. Here we demonstrate that it is an oversimplified view that these shape corrections concern primarily the asymptotic part of the potential, and that they affect only Rydberg type transitions. The performance is assessed of two shape-corrected Kohn-Sham potentials, the gradient-regulated asymptotic connection procedure applied to the Becke-Perdew potential (BP-GRAC) and the statistical averaging of (model) orbital potentials (SAOP), versus LDA and GGA potentials, in molecular response calculations of the static average polarizability alpha, the Cauchy coefficient S-4, and the static average hyperpolarizability beta. The nature of the distortions of the LDA/GGA potentials is highlighted and it is shown that they introduce many spurious excited states at too low energy which may mix with valence excited states, resulting in wrong excited state compositions. They also lead to wrong oscillator strengths and thus to a wrong spectral structure of properties like the polarizability. LDA, Becke-Lee-Yang-Parr (BLYP), and Becke-Perdew (BP) characteristically underestimate contributions to alpha and S-4 from bound Rydberg-type states and overestimate those from the continuum. Cancellation of the errors in these contributions occasionally produces fortuitously good results. The distortions of the LDA, BLYP, and BP spectra are related to the deficiencies of the LDA/GGA potentials in both the bulk and outer molecular regions. In contrast, both SAOP and BP-GRAC potentials produce high quality polarizabilities for 21 molecules and also reliable Cauchy moments and hyperpolarizabilities for the selected molecules. The analysis for the N-2 molecule shows, that both SAOP and BP-GRAC yield reliable energies omega(i) and oscillator strengths f(i) of individual excitations, so that they reproduce well the spectral structure of alpha and S-4.(C) 2002 American Institute of Physics.

The failure of generalized gradient approximations (GGAs) and meta-GGAs for the two-center three-electron bonds in He-2(+), (H2O)(2)(+), and (NH3)(2)(+)

The radical cations He-2(+) (H2O)(2)(+), and (NH3)(2)(+) with two-center three-electron A-A bonds are investigated at the configuration interaction (CI), accurate Kohn-Sham (KS), generalized gradient approximation (GGA), and meta-GGA levels. Assessment of seven different GGA and six meta-GGA methods shows that the A(2)(+) systems remain a difficult case for density functional theory (DFT). All methods tested consistently overestimate the stability of A(2)(+): the corresponding D-e errors decrease for more diffuse valence densities in the series He-2(+) > (H2O)(2)(+) > (NH3)(2)(+). Upon comparison to the energy terms of the accurate Kohn-Sham solutions, the approximate exchange functionals are found to be responsible for the errors of GGA-type methods, which characteristically overestimate the exchange in A(2)(+). These so-called exchange functionals implicitly use localized holes. Such localized holes do occur if there is left-right correlation, i.e., the exchange functionals then also describe nondynamical correlation. However, in the hemibonded A(2)(+) systems the typical molecular (left-right, nondynamical) correlation of the two-electron pair bond is absent. The nondynamical correlation built into the exchange functionals is then spurious and yields too low energies.

Analytical approximations to numerical solutions of theoretical emission measure distributions

Emission line fluxes from cool stars are widely used to establish an apparent emission measure distribution, EmdApp(Te), between temperatures characteristic of the low transition region and the low corona. The true emission measure distribution, EmdTrue(Te), is determined by the energy balance and geometry adopted and, with a numerical model, can be used to predict EmdApp(Te), to guide further modelling. The scaling laws that exist between coronal parameters arise from the dimensions of the terms in the energy balance equation. Here, analytical approximations to numerical solutions for EmdTrue(Te) are presented, which show how the constants in the coronal scaling laws are determined. The apparent emission measure distributions show a minimum value at some T0 and a maximum at the mean coronal temperature Tc (although in some stars, emission from active regions can contribute). It is shown that, for the energy balance and geometry adopted, the analytical values of the emission measure and electron pressure at T0 and Tc depend on only three parameters: the stellar surface gravity and the values of T0 and Tc. The results are tested against full numerical solutions for e Eri (K2 V) and are applied to Procyon (a CMi, F5 IV/V). The analytical approximations can be used to restrict the required range of full numerical solutions, to check the assumed geometry and to show where the adopted energy balance may not be appropriate. © 2011 The Authors Monthly Notices of the Royal Astronomical Society © 2011 RAS.

Fractional derivatives: probability interpretation and frequency response of rational approximations

The theory of fractional calculus (FC) is a useful mathematical tool in many applied sciences. Nevertheless, only in the last decades researchers were motivated for the adoption of the FC concepts. There are several reasons for this state of affairs, namely the co-existence of different definitions and interpretations, and the necessity of approximation methods for the real time calculation of fractional derivatives (FDs). In a first part, this paper introduces a probabilistic interpretation of the fractional derivative based on the Grünwald-Letnikov definition. In a second part, the calculation of fractional derivatives through Padé fraction approximations is analyzed. It is observed that the probabilistic interpretation and the frequency response of fraction approximations of FDs reveal a clear correlation between both concepts.

Asymptotic Approximations in the Near-Integrated Model with a Non-Zero Initial Condition

This paper considers various asymptotic approximations in the near-integrated firstorder autoregressive model with a non-zero initial condition. We first extend the work of Knight and Satchell (1993), who considered the random walk case with a zero initial condition, to derive the expansion of the relevant joint moment generating function in this more general framework. We also consider, as alternative approximations, the stochastic expansion of Phillips (1987c) and the continuous time approximation of Perron (1991). We assess how these alternative methods provide or not an adequate approximation to the finite-sample distribution of the least-squares estimator in a first-order autoregressive model. The results show that, when the initial condition is non-zero, Perron's (1991) continuous time approximation performs very well while the others only offer improvements when the initial condition is zero.