Habib AmmariDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceThomas BoulierDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceJosselin GarnierLaboratoire de Probabilités et Modèles Aléatoires & Laboratoire Jacques-Louis Lions, Université Paris VII, 75205, Paris Cedex 13, FranceWenjia JingDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, FranceHyeonbae KangDepartment of Mathematics, Inha University, Incheon, 402-751, KoreaHan WangDepartment of Mathematics and Applications, Ecole Normale Supérieure, 45 Rue d’Ulm, 75005, Paris, France
Analysis of PDEsMathematical PhysicsNumerical Analysis and Scientific ComputingOptimization and Controlmathscidoc:2206.03006
Foundations of Computational Mathematics, 14, 27-62, 2013.9
The aim of this paper is to provide a fast and efficient procedure for (real-time) target identification in imaging based on matching on a dictionary of precomputed generalized polarization tensors (GPTs). The approach is based on some important properties of the GPTs and new invariants. A new shape representation is given and numerically tested in the presence of measurement noise. The stability and resolution of the proposed identification algorithm is numerically quantified. We compare the proposed GPT-based shape representation with a moment-based one.
Chenchen MouDepartment of Mathematics, City University of Hong Kong, Hong Kong, ChinaXianjin YangYau Mathematical Sciences Center, Tsinghua University, Haidian District, Beijing, 100084, China; Beijing Institute of Mathematical Sciences and Applications, Huairou District, Beijing, 101408, ChinaChao ZhouDepartment of Mathematics and Risk Management Institute, National University of Singapore, Singapore
Numerical Analysis and Scientific ComputingOptimization and Controlmathscidoc:2206.25007
Journal of Computational Physics, 460, (1), 111188, 2022.7
In this article, we propose two numerical methods, the Gaussian Process (GP) method and the Fourier Features (FF) algorithm, to solve mean field games (MFGs). The GP algorithm approximates the solution of a MFG with maximum a posteriori probability estimators of GPs conditioned on the partial differential equation (PDE) system of the MFG at a finite number of sample points. The main bottleneck of the GP method is to compute the inverse of a square gram matrix, whose size is proportional to the number of sample points. To improve the performance, we introduce the FF method, whose insight comes from the recent trend of approximating positive definite kernels with random Fourier features. The FF algorithm seeks approximated solutions in the space generated by sampled Fourier features. In the FF method, the size of the matrix to be inverted depends only on the number of Fourier features selected, which is much less than the size of sample points. Hence, the FF method reduces the precomputation time, saves the memory, and achieves comparable accuracy to the GP method. We give the existence and the convergence proofs for both algorithms. The convergence argument of the GP method does not depend on any monotonicity condition, which suggests the potential applications of the GP method to solve MFGs with non-monotone couplings in future work. We show the efficacy of our algorithms through experiments on a stationary MFG with a non-local coupling and on a time-dependent planning problem. We believe that the FF method can also serve as an alternative algorithm to solve general PDEs.
Ruichen JiangDepartment of Electronic Engineering, Tsinghua University, Beijing 100084, ChinaYa-Feng LiuState Key Laboratory of Scientific and Engineering Computing, Institute of Computational Mathematics and Scientific/Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, ChinaChenglong BaoYau Mathematical Sciences Center, Tsinghua University, Beijing 100084, ChinaBo JiangSchool of Mathematical Sciences, Key Laboratory for NSLSCS of Jiangsu Province, Nanjing Normal University, Nanjing 210023, China
The multiple-input multiple-output (MIMO) detection problem, a fundamental problem in modern digital communications, is to detect a vector of transmitted symbols from the noisy outputs of a fading MIMO channel. The maximum likelihood detector can be formulated as a complex least-squares problem with discrete variables, which is NP-hard in general. Various semidefinite relaxation (SDR) methods have been proposed in the literature to solve the problem due to their polynomial-time worst-case complexity and good detection error rate performance. In this paper, we consider two popular classes of SDR-based detectors and study the conditions under which the SDRs are tight and the relationship between different SDR models. For the enhanced complex and real SDRs proposed recently by Lu et al., we refine their analysis and derive the necessary and sufficient condition for the complex SDR to be tight, as well as a necessary condition for the real SDR to be tight. In contrast, we also show that another SDR proposed by Mobasher et al. is not tight with high probability under mild conditions. Moreover, we establish a general theorem that shows the equivalence between two subsets of positive semidefinite matrices in different dimensions by exploiting a special "separable" structure in the constraints. Our theorem recovers two existing equivalence results of SDRs defined in different settings and has the potential to find other applications due to its generality.