We study a type of Riemannian gradient descent (RGD) algorithm, designed through Riemannian preconditioning, for optimization on $\mathcal{M}_k^{m\times n}$ -- the set of $m\times n$ real matrices with a fixed rank $k$. Our analysis is based on a quotient geometric view of $\mathcal{M}_k^{m\times n}$: by identifying this set with the quotient manifold of a two-term product space $\mathbb{R}_*^{m\times k}\times \mathbb{R}_*^{n\times k}$ of matrices with full column rank via matrix factorization, we find an explicit form for the update rule of the RGD algorithm, which leads to a novel approach to analysing their convergence behavior in rank-constrained optimization. We then deduce some interesting properties that reflect how RGD distinguishes from other matrix factorization algorithms such as those based on the Euclidean geometry. In particular, we show that the RGD algorithm is not only faster than Euclidean gradient descent but also does not rely on balancing techniques to ensure its efficiency while the latter does. We further show that this RGD algorithm is guaranteed to solve matrix sensing and matrix completion problems with linear convergence rate under the restricted positive definiteness property. Numerical experiments on matrix sensing and completion are provided to demonstrate these properties.
相關內容
We present a rigorous convergence analysis of a new method for density-based topology optimization: Sigmoidal Mirror descent with a Projected Latent variable. SiMPL provides point-wise bound preserving design updates and faster convergence than other popular first-order topology optimization methods. Due to its strong bound preservation, the method is exceptionally robust, as demonstrated in numerous examples here and in a companion article. Furthermore, it is easy to implement with clear structure and analytical expressions for the updates. Our analysis covers two versions of the method, characterized by the employed line search strategies. We consider a modified Armijo backtracking line search and a Bregman backtracking line search. Regardless of the line search algorithm, SiMPL delivers a strict monotone decrease in the objective function and further intuitive convergence properties, e.g., strong and pointwise convergence of the density variables on the active sets, norm convergence to zero of the increments, and more. In addition, the numerical experiments demonstrate apparent mesh-independent convergence of the algorithm and superior performance over the two most popular first-order methods in topology optimization: OC and MMA.
We derive a robust error estimate for a recently proposed numerical method for $\alpha$-dissipative solutions of the Hunter-Saxton equation, where $\alpha \in [0, 1]$. In particular, if the following two conditions hold: i) there exist a constant $C > 0$ and $\beta \in (0, 1]$ such that the initial spatial derivative $\bar{u}_{x}$ satisfies $\|\bar{u}_x(\cdot + h) - \bar{u}_x(\cdot)\|_2 \leq Ch^{\beta}$ for all $h \in (0, 2]$, and ii), the singular continuous part of the initial energy measure is zero, then the numerical wave profile converges with order $O(\Delta x^{\frac{\beta}{8}})$ in $L^{\infty}(\mathbb{R})$. Moreover, if $\alpha=0$, then the rate improves to $O(\Delta x^{\frac{1}{4}})$ without the above assumptions, and we also obtain a convergence rate for the associated energy measure - it converges with order $O(\Delta x^{\frac{1}{2}})$ in the bounded Lipschitz metric. These convergence rates are illustrated by several examples.
The main purpose of this paper is to design a local discontinuous Galerkin (LDG) method for the Benjamin-Ono equation. We analyze the stability and error estimates for the semi-discrete LDG scheme. We prove that the scheme is $L^2$-stable and it converges at a rate $\mathcal{O}(h^{k+1/2})$ for general nonlinear flux. Furthermore, we develop a fully discrete LDG scheme using the four-stage fourth order Runge-Kutta method and ensure the devised scheme is strongly stable in case of linear flux using two-step and three-step stability approach under an appropriate time step constraint. Numerical examples are provided to validate the efficiency and accuracy of the method.
In this work, we develop Crank-Nicolson-type iterative decoupled algorithms for a three-field formulation of Biot's consolidation model using total pressure. We begin by constructing an equivalent fully implicit coupled algorithm using the standard Crank-Nicolson method for the three-field formulation of Biot's model. Employing an iterative decoupled scheme to decompose the resulting coupled system, we derive two distinctive forms of Crank-Nicolson-type iterative decoupled algorithms based on the order of temporal computation and iteration: a time-stepping iterative decoupled algorithm and a global-in-time iterative decoupled algorithm. Notably, the proposed global-in-time algorithm supports a partially parallel-in-time feature. Capitalizing on the convergence properties of the iterative decoupled scheme, both algorithms exhibit second-order time accuracy and unconditional stability. Through numerical experiments, we validate theoretical predictions and demonstrate the effectiveness and efficiency of these novel approaches.
Predicting the response of nonlinear dynamical systems subject to random, broadband excitation is important across a range of scientific disciplines, such as structural dynamics and neuroscience. Building data-driven models requires experimental measurements of the system input and output, but it can be difficult to determine whether inaccuracies in the model stem from modelling errors or noise. This paper presents a novel method to identify the causal component of the input-output data from measurements of a system in the presence of output noise, as a function of frequency, without needing a high fidelity model. An output prediction, calculated using an available model, is optimally combined with noisy measurements of the output to predict the input to the system. The parameters of the algorithm balance the two output signals and are utilised to calculate a nonlinear coherence metric as a measure of causality. This method is applicable to a broad class of nonlinear dynamical systems. There are currently no solutions to this problem in the absence of a complete benchmark model.
To solve the Cahn-Hilliard equation numerically, a new time integration algorithm is proposed, which is based on a combination of the Eyre splitting and the local iteration modified (LIM) scheme. The latter is employed to tackle the implicit system arising each time integration step. The proposed method is gradient-stable and allows to use large time steps, whereas, regarding its computational structure, it is an explicit time integration scheme. Numerical tests are presented to demonstrate abilities of the new method and to compare it with other time integration methods for Cahn-Hilliard equation.
Approximating solutions of ordinary and partial differential equations constitutes a significant challenge. Based on functional expressions that inherently depend on neural networks, neural forms are specifically designed to precisely satisfy the prescribed initial or boundary conditions of the problem, while providing the approximate solutions in closed form. Departing from the important class of ordinary differential equations, the present work aims to refine and validate the neural forms methodology, paving the ground for further developments in more challenging fields. The main contributions are as follows. First, it introduces a formalism for systematically crafting proper neural forms with adaptable boundary matches that are amenable to optimization. Second, it describes a novel technique for converting problems with Neumann or Robin conditions into equivalent problems with parametric Dirichlet conditions. Third, it outlines a method for determining an upper bound on the absolute deviation from the exact solution. The proposed augmented neural forms approach was tested on a set of diverse problems, encompassing first- and second-order ordinary differential equations, as well as first-order systems. Stiff differential equations have been considered as well. The resulting solutions were subjected to assessment against existing exact solutions, solutions derived through the common penalized neural method, and solutions obtained via contemporary numerical analysis methods. The reported results demonstrate that the augmented neural forms not only satisfy the boundary and initial conditions exactly, but also provide closed-form solutions that facilitate high-quality interpolation and controllable overall precision. These attributes are essential for expanding the application field of neural forms to more challenging problems that are described by partial differential equations.
Dependencies among attributes are a common aspect of tabular data. However, whether existing tabular data generation algorithms preserve these dependencies while generating synthetic data is yet to be explored. In addition to the existing notion of functional dependencies, we introduce the notion of logical dependencies among the attributes in this article. Moreover, we provide a measure to quantify logical dependencies among attributes in tabular data. Utilizing this measure, we compare several state-of-the-art synthetic data generation algorithms and test their capability to preserve logical and functional dependencies on several publicly available datasets. We demonstrate that currently available synthetic tabular data generation algorithms do not fully preserve functional dependencies when they generate synthetic datasets. In addition, we also showed that some tabular synthetic data generation models can preserve inter-attribute logical dependencies. Our review and comparison of the state-of-the-art reveal research needs and opportunities to develop task-specific synthetic tabular data generation models.
Error estimates of cubic interpolated pseudo-particle scheme (CIP scheme) for the one-dimensional advection equation with periodic boundary conditions are presented. The CIP scheme is a semi-Lagrangian method involving the piecewise cubic Hermite interpolation. Although it is numerically known that the space-time accuracy of the scheme is third order, its rigorous proof remains an open problem. In this paper, denoting the spatial and temporal mesh sizes by $ h $ and $ \Delta t $ respectively, we prove an error estimate $ O(\Delta t^3 + \frac{h^4}{\Delta t}) $ in $ L^2 $ norm theoretically, which justifies the above-mentioned prediction if $ h = O(\Delta t) $. The proof is based on properties of the interpolation operator; the most important one is that it behaves as the $ L^2 $ projection for the second-order derivatives. We remark that the same strategy perfectly works as well to address an error estimate for the semi-Lagrangian method with the cubic spline interpolation.
We study the decidability and complexity of non-cooperative rational synthesis problem (abbreviated as NCRSP) for some classes of probabilistic strategies. We show that NCRSP for stationary strategies and Muller objectives is in 3-EXPTIME, and if we restrict the strategies of environment players to be positional, NCRSP becomes NEXPSPACE solvable. On the other hand, NCRSP_>, which is a variant of NCRSP, is shown to be undecidable even for pure finite-state strategies and terminal reachability objectives. Finally, we show that NCRSP becomes EXPTIME solvable if we restrict the memory of a strategy to be the most recently visited t vertices where t is linear in the size of the game.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191