Robust sparse phase retrieval made easy

In this short note we propose a simple two-stage sparse phase retrieval strategy that uses a near-optimal number of measurements, and is both computationally efficient and robust to measurement noise. In addition, the proposed strategy is fairly general, allowing for a large number of new measurement constructions and recovery algorithms to be designed with minimal effort.     

Robust reconstruction of the discrete state for a class of nonlinear uncertain switched systems

This paper presents an approach to the robust state reconstruction for a class of nonlinear switched systems affected by model uncertainties. Under the assumption that the continuous state is available for measurement, an approach is presented based on concepts and methodologies derived from the sliding mode control theory. With noise-free state measurements, the time needed for reconstructing the discrete state after a transition can be made arbitrarily small by sufficiently increasing a certain observer tuning parameter. Simulations and experiments, carried out on a three-tank laboratory setup, are presented and commented.     

The Minimal Measurement Number Problem in Phase Retrieval: A Review of Recent Developments

Phase retrieval is to recover the signals from phaseless measurements which is raised in many areas. A fundamental problem in phase retrieval is to determine the minimal measurement number $m$ so that one can recover $d$-dimensional signals from $m$ phaseless measurements. This problem attracts much attention of experts from different areas. In this paper, we review the recent development on the minimal measurement number and also raise many interesting open questions.     

Morrey’s Conjecture for the Planar Volumetric-Isochoric Split: Least Rank-One Convex Energy Functions

Sensor placement and feature selection are critical steps in engineering, modeling, and data science that share a common mathematical theme: the selected measurements should enable solution of an inverse problem. Most real-world systems of interest are nonlinear, yet the majority of available techniques for feature selection and sensor placement rely on assumptions of linearity or simple statistical models. We show that when these assumptions are violated, standard techniques can lead to costly over-sensing without guaranteeing that the desired information can be recovered from the measurements. In order to remedy these problems, we introduce a novel data-driven approach for sensor placement and feature selection for a general type of nonlinear inverse problem based on the information contained in secant vectors between data points. Using the secant-based approach, we develop three efficient greedy algorithms that each provide different types of robust, near-minimal reconstruction guarantees. We demonstrate them on two problems where linear techniques consistently fail: sensor placement to reconstruct a fluid flow formed by a complicated shock–mixing layer interaction and selecting fundamental manifold learning coordinates on a torus.

     

Solution to the Mean King's Problem in Prime Power Dimensions Using Discrete Tomography

We solve a state reconstruction problem which arises in quantum information and which generalizes a problem introduced by Vaidman, Aharonov, and Albert in 1987. The task is to correctly predict the outcome of a measurement which an experimenter performed secretly in a lab. Using tomographic reconstruction based on summation over lines in an affine geometry, we show that this is possible whenever the measurements form a maximal set of mutually unbiased bases. Using a different approach we show that if the dimension of the system is large, the measurement result as well as the secretly chosen measurement basis can be inferred with high probability. This can be achieved even when the meanspirited King is unwilling to reveal the measurement basis at any point in time.     

Stable Gabor Phase Retrieval and Spectral Clustering

We consider the problem of reconstructing a signal f from its spectrogram, i.e., the magnitudes |V_φf| of its Gabor transform Such problems occur in a wide range of applications, from optical imaging of nanoscale structures to audio processing and classification. While it is well-known that the solution of the above Gabor phase retrieval problem is unique up to natural identifications, the stability of the reconstruction has remained wide open. The present paper discovers a deep and surprising connection between phase retrieval, spectral clustering, and spectral geometry. We show that the stability of the Gabor phase reconstruction is bounded by the reciprocal of the Cheeger constant of the flat metric on ℝ², conformally multiplied with |V_φf|. The Cheeger constant, in turn, plays a prominent role in the field of spectral clustering, and it precisely quantifies the “disconnectedness” of the measurements V_φf. It has long been known that a disconnected support of the measurements results in an instability—our result for the first time provides a converse in the sense that there are no other sources of instabilities. Due to the fundamental importance of Gabor phase retrieval in coherent diffraction imaging, we also provide a new understanding of the stability properties of these imaging techniques: Contrary to most classical problems in imaging science whose regularization requires the promotion of smoothness or sparsity, the correct regularization of the phase retrieval problem promotes the “connectedness” of the measurements in terms of bounding the Cheeger constant from below. Our work thus, for the first time, opens the door to the development of efficient regularization strategies. © 2018 Wiley Periodicals, Inc.     

Phase Retrieval of Real-valued Functions in Sobolev Space

The Sobolev space H^s(R^d) with s > d/2 contains many important functions such as the bandlimited or rational ones. In this paper we propose a sequence of measurement functions {ϕ_j,k^γ} ⊆ H^-s(R^d) to the phase retrieval problem for the real-valued functions in H^s(R^d). We prove that any real-valued function f ∈ H^s(R^d) can be determined, up to a global sign, by the phaseless measurements {|<f, ϕ_j,k^γ>|}. It is known that phase retrieval is unstable in infinite dimensional spaces with respect to perturbations of the measurement functions. We examine a special type of perturbations that ensures the stability for the phase-retrieval problem for all the real-valued functions in H^s(R^d) ∩ C¹(R^d), and prove that our iterated reconstruction procedure guarantees uniform convergence for any function f ∈ H^s(R^d) ∩ C¹(R^d) whose Fourier transform f is L¹-integrable. Moreover, numerical simulations are conducted to test the efficiency of the reconstruction algorithm.     

AN EXTENDED BLOCK RESTRICTED ISOMETRY PROPERTY FOR SPARSE RECOVERY WITH NON-GAUSSIAN NOISE

We study the recovery conditions of weighted mixed $\ell_2/\ell_p$ minimization for block sparse signal reconstruction from compressed measurements when partial block support information is available. We show theoretically that the extended block restricted isometry property can ensure robust recovery when the data fidelity constraint is expressed in terms of an $\ell_q$ norm of the residual error, thus establishing a setting wherein we are not restricted to Gaussian measurement noise. We illustrate the results with a series of numerical experiments.     

Local linear convergence of approximate projections onto regularized sets

The numerical properties of algorithms for finding the intersection of sets depend to some extent on the regularity of the sets, but even more importantly on the regularity of the intersection. The alternating projection algorithm of von Neumann has been shown to converge locally at a linear rate dependent on the regularity modulus of the intersection. In many applications, however, the sets in question come from inexact measurements that are matched to idealized models. It is unlikely that any such problems in applications will enjoy metrically regular intersection, let alone set intersection. We explore a regularization strategy that generates an intersection with the desired regularity properties. The regularization, however, can lead to a significant increase in computational complexity. In a further refinement, we investigate and prove linear convergence of an approximate alternating projection algorithm. The analysis provides a regularization strategy that fits naturally with many ill-posed inverse problems, and a mathematically sound stopping criterion for extrapolated, approximate algorithms. The theory is demonstrated on the phase retrieval problem with experimental data. The conventional early termination applied in practice to unregularized, consistent problems in diffraction imaging can be justified fully in the framework of this analysis providing, for the first time, proof of convergence of alternating approximate projections for finite dimensional, consistent phase retrieval problems.     

Phaseless inverse discrete Hilbert transform and determination of signals in shift‐invariant space

In this paper, we first address the uniqueness of phaseless inverse discrete Hilbert transform (phaseless IDHT for short) from the magnitude of discrete Hilbert transform (DHT for short). The measurement vectors of phaseless IDHT do not satisfy the complement property, a traditional requirement for ensuring the uniqueness of phase retrieval. Consequently, the uniqueness problem of phaseless IDHT is essentially different from that of the traditional phase retrieval. For the phaseless IDHT related to compactly supported functions, conditions are given in our first main theorem to ensure the uniqueness. A condition on the step size of DHT is crucial for the insurance. The second main theorem concerns the uniqueness related to noncompactly supported functions. It is not the trivial generalization of the first main theorem. Our third main result is on the determination of signals in shift‐invariant spaces by phaseless IDHT. Note that the measurements used for the determination are the DHT magnitudes. They are the approximations to the Hilbert transform magnitudes. Recall that for the existing methods of phaseless sampling (a special phase‐retrieval problem), to determine a signal depends on the exact measurements but not the approximative ones. Therefore, our determination method is essentially different from the traditional phaseless sampling. Numerical simulations are conducted to examine the efficiency of phaseless IDHT and its application in determining signals in spline Hilbert shift‐invariant space.     

A coupled complex boundary method for an inverse conductivity problem with one measurement

We recently proposed in [Cheng, XL et al. A novel coupled complex boundary method for inverse source problems Inverse Problem 2014 30 055002] a coupled complex boundary method (CCBM) for inverse source problems. In this paper, we apply the CCBM to inverse conductivity problems (ICPs) with one measurement. In the ICP, the diffusion coefficient q is to be determined from both Dirichlet and Neumann boundary data. With the CCBM, q is sought such that the imaginary part of the solution of a forward Robin boundary value problem vanishes in the problem domain. This brings in advantages on robustness and computation in reconstruction. Based on the complex forward problem, the Tikhonov regularization is used for a stable reconstruction. Some theoretical analysis is given on the optimization models. Several numerical examples are provided to show the feasibility and usefulness of the CCBM for the ICP. It is illustrated that as long as all the subdomains share some portion of the boundary, our CCBM-based Tikhonov regularization method can reconstruct the diffusion parameters stably and effectively.     

Angular Synchronization by Eigenvectors and Semidefinite Programming

The angular synchronization problem is to obtain an accurate estimation (up to a constant additive phase) for a set of unknown angles θ(1), …, θ(n) from m noisy measurements of their offsets θ(i) - θ(j) mod 2π. Of particular interest is angle recovery in the presence of many outlier measurements that are uniformly distributed in [0, 2π) and carry no information on the true offsets. We introduce an efficient recovery algorithm for the unknown angles from the top eigenvector of a specially designed Hermitian matrix. The eigenvector method is extremely stable and succeeds even when the number of outliers is exceedingly large. For example, we successfully estimate n = 400 angles from a full set of m=(4002) offset measurements of which 90% are outliers in less than a second on a commercial laptop. The performance of the method is analyzed using random matrix theory and information theory. We discuss the relation of the synchronization problem to the combinatorial optimization problem Max-2-Lin mod L and present a semidefinite relaxation for angle recovery, drawing similarities with the Goemans-Williamson algorithm for finding the maximum cut in a weighted graph. We present extensions of the eigenvector method to other synchronization problems that involve different group structures and their applications, such as the time synchronization problem in distributed networks and the surface reconstruction problems in computer vision and optics.     

A robust nonparametric approach to evaluate and explain the performance of mutual funds

The topic of the measurement of mutual funds’ performance is receiving an increasing interest both from an applied and a theoretical perspective. Beside the traditional financial literature, a growing body of studies has started to apply the tools of frontier analysis for benchmarking comparisons in portfolio analysis. Our paper contributes to this literature proposing a robust nonparametric approach for analysing mutual funds. It is based on the concept of order-m frontier [Cazals, C., Florens, J.P., Simar, L., 2002. Nonparametric frontier estimation: A robust approach. Journal of Econometrics 106, 1–25] and on a probabilistic approach [Daraio, C., Simar, L., 2005. Introducing environmental variables in nonparametric frontier models: A probabilistic approach. Journal of Productivity Analysis 24 (1), 93–121] to find out the factors explaining mutual funds’ performance. Within this framework, a decomposition of conditional efficiency is proposed, and its usefulness for economic interpretation analysed. Our approach is illustrated by using US mutual funds data, grouped for category by objective. Economies of scale, slacks and market risks are investigated. A comparison of traditional, nonparametric and robust performance measures is also offered.     

Refined Analysis of Sparse MIMO Radar

We analyze a multiple-input multiple-output (MIMO) radar model and provide recovery results for a compressed sensing (CS) approach. In MIMO radar different pulses are emitted by several transmitters and the echoes are recorded at several receiver nodes. Under reasonable assumptions the transformation from emitted pulses to the received echoes can approximately be regarded as linear. For the considered model, and many radar tasks in general, sparsity of targets within the considered angle-range-Doppler domain is a natural assumption. Therefore, it is possible to apply methods from CS in order to reconstruct the parameters of the targets. Assuming Gaussian random pulses the resulting measurement matrix becomes a highly structured random matrix. Our first main result provides an estimate for the well-known restricted isometry property (RIP) ensuring stable and robust recovery. We require more measurements than standard results from CS, like for example those for Gaussian random measurements. Nevertheless, we show that due to the special structure of the considered measurement matrix our RIP result is in fact optimal (up to possibly logarithmic factors). Our further two main results on nonuniform recovery (i.e., for a fixed sparse target scene) reveal how the fine structure of the support set—not only the size—affects the (nonuniform) recovery performance. We show that for certain “balanced” support sets reconstruction with essentially the optimal number of measurements is possible. Indeed, we introduce a parameter measuring the well-behavedness of the support set and resemble standard results from CS for near-optimal parameter choices. We prove recovery results for both perfect recovery of the support set in case of exactly sparse vectors and an \(\ell _2\)-norm approximation result for reconstruction under sparsity defect. Our analysis complements earlier work by Strohmer & Friedlander and deepens the understanding of the considered MIMO radar model. Thereby—and apparently for the first time in CS theory—we prove theoretical results in which the difference between nonuniform and uniform recovery consists of more than just logarithmic factors.     

Statistical inverse problems: Discretization,model reduction and inverse crimes

The article discusses the discretization of linear inverse problems. When an inverse problem is formulated in terms of infinite-dimensional function spaces and then discretized for computational purposes, a discretization error appears. Since inverse problems are typically ill-posed, neglecting this error may have serious consequences to the quality of the reconstruction. The Bayesian paradigm provides tools to estimate the statistics of the discretization error that is made part of the measurement and modelling errors of the estimation problem. This approach also provides tools to reduce the dimensionality of inverse problems in a controlled manner. The ideas are demonstrated with a computed example.     

Asymptotic Formulas for Thermography Based Recovery of Anomalies

We start from a realistic half space model for thermal imaging, which we then use to develop a mathematical asymptotic analysis well suited for the design of reconstruction algorithms. We seek to reconstruct thermal anomalies only through their rough features. With this way our proposed algorithms are stable against measurement noise and geometry perturbations. Based on rigorous asymptotic estimates, we first obtain an approximation for the temperature profile which we then use to design nonit-erative detection algorithms. We show on numerical simulations evidence that they are accurate and robust. Moreover, we provide a mathematical model for ultrasonic temperature imaging, which is an important technique in cancerous tissue ablation therapy.AMS subject classifications: 35R20, 35B30     

Stable Signal Recovery from Phaseless Measurements

The aim of this paper is to study the stability of the \(\ell _1\) minimization for the compressive phase retrieval and to extend the instance-optimality in compressed sensing to the real phase retrieval setting. We first show that \(m={\mathcal {O}}(k\log (N/k))\) measurements are enough to guarantee the \(\ell _1\) minimization to recover k-sparse signals stably provided the measurement matrix A satisfies the strong RIP property. We second investigate the phaseless instance-optimality presenting a null space property of the measurement matrix A under which there exists a decoder \(\Delta \) so that the phaseless instance-optimality holds. We use the result to study the phaseless instance-optimality for the \(\ell _1\) norm. This builds a parallel for compressive phase retrieval with the classical compressive sensing.     

An Interior-Point Method for a Class of Saddle-Point Problems

We present a polynomial-time interior-point algorithm for a class of nonlinear saddle-point problems that involve semidefiniteness constraints on matrix variables. These problems originate from robust optimization formulations of convex quadratic programming problems with uncertain input parameters. As an application of our approach, we discuss a robust formulation of the Markowitz portfolio selection model.     

Robust Parameter Estimation for Stochastic Differential Equations

We consider the estimation of parameters in stochastic differential equations (SDEs). The problem is treated in the setting of nonlinear filtering theory with a degenerate diffusion matrix. A robust stochastic Feynman–Kac representation for solutions of SDEs of Zakai-type is derived. It is verified that these solutions are conditional densities for the conditional measures defined by degenerate filtering problems. We show that the corresponding estimator for the parameters is robust in the following sense: It depends continuously on both the measurement path and on the intensity of the measurement noise. An algorithm based on a Monte-Carlo approach is given for the practical application of the estimator, and numerical results are reported. Mathematics Subject Classifications (2000) Primary: 62M05, 62M20; secondary: 62F15.     

基于时间序列建模和控制图的异常交易检测方法

可疑交易识别是打击洗钱犯罪所要面对的一项重要任务.为辅助反洗钱分析人员从海量金融交易信息中甄别客户异常交易,本文提出一种新的基于非线性马尔科夫随机过程、相空间重构和隐马尔科夫链的非线性随机方法,用于对金融交易时序进行建模拟合,然后应用鲁棒控制图对估计误差进行检验以发现异常.应用该算法对实际交易数据和仿真数据的分析验证了所提方法的有效性和可行性,可以被用于异常交易的监测.