Quantum algorithm for neighborhood preserving embedding

Neighborhood preserving embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality n. However, the algorithm has two disadvantages: (i) It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one. (ii) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm, and achieve a significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.     

全局优化问题的一个新的无参数填充函数

求全局最优化问题的填充函数算法被提出以来，参数的选取和调整一直是制约算法有效性的因素。如何在实际的计算过程中选取合适的参数，直接影响和决定了运算速度和效率。因此，构造不含参数的填充函数就显得极为重要。提出一个新的无参数的填充函数，对其理论性质进行了分析，并给出相应的填充函数算法，数值计算验证了算法的有效性。     

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and sensor placement problems in control, task allocation problems, video summarization, and many others. We study two greedy heuristics, namely, the forward and reverse greedy. We provide two novel performance guarantees for the approximate solutions obtained by them depending on both submodularity ratio and curvature.     

Classical solution for a nonlinear hybrid system modeling combustion in a multilayer porous medium

Combustion processes in porous media have been used by the petroleum engineering industry to extract heavy oil from reservoirs. This study focuses on a one-dimensional nonlinear hybrid system consisting of $n$ reaction–diffusion–convection equations coupled with $n$ ordinary differential equations, which models a combustion front moving through a porous medium with $n$ parallel layers. The state variables are the temperature and fuel concentration in each layer. Coupling occurs in both the reaction function and differential operator coefficients. We prove the existence of a classical solution, first locally and then globally over time, to an initial and boundary value problem for the corresponding system. The proof uses a new approach for combustion problems in porous media. The local solution is obtained by defining an operator in a set of Hölder continuous functions and using Schauder’s fixed-point theorem to find a fixed point as the desired solution. Using Zorn’s lemma, we extend the local solution to a global solution, proving that the first-order spatial derivative of the temperature in each layer is a bounded function.     

Hilbert’s Nullstellensatz for analytic trigonometric polynomials

This paper proves such a new Hilbert’s Nullstellensatz for analytic trigonometric polynomials that if ${\left\{f_j\right\}}_{j=1}^{n\ge 2}$ are analytic trigonometric polynomials without common zero in the finite complex plane $?$ then there are analytic trigonometric polynomials ${\left\{g_j\right\}}_{j=1}^{n\ge 2}$ obeying ${\sum }_{j=1}^{n\ge 2}{f}_j{g}_j=1$ in $?$, thereby not only strengthening Helmer’s Principal Ideal Theorem for entire functions, but also finding an intrinsic path from Hilbert’s Nullstellensatz for analytic polynomials to Pythagoras’ Identity on $?$.     

A new idea to construct the fractal interpolation function

The aim of this paper is to present a new idea to construct the nonlinear fractal interpolation function, in which we exploit the Matkowski and the Rakotch fixed point theorems. Our technique is different from the methods presented in the previous literatures.     

求解矩阵方程AXB+CXD=F参数迭代法的最优参数分析

本文针对求矩阵方程AXB+CXD=F唯一解的参数迭代法，分析当矩阵A，B，C，D均是Hermite正（负）定矩阵时，迭代矩阵的特征值表达式，给出了最优参数的确定方法，并提出了相应的加速算法.     

Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

Non-singular Green’s functions for the unbounded Poisson equation in one,two and three dimensions

In this paper, we derive the non-singular Green’s functions for the unbounded Poisson equation in one, two and three dimensions using a spectral cut-off function approach to impose a minimum length scale in the homogeneous solution. The resulting non-singular Green’s functions are relevant to applications which are restricted to a minimum resolved length scale (e.g. a mesh size $h$) and thus cannot handle the singular Green’s function of the continuous Poisson equation. We furthermore derive the gradient vector of the non-singular Green’s function, as this is useful in applications where the Poisson equation represents potential functions of a vector field.     

Chase’s lemma and its context

Chase’s lemma provides a powerful tool for translating properties of (co)products in abelian categories into chain conditions. This note discusses the context in which the lemma is used, making explicit what is often neglected in the literature because of its technical nature.