Resolution analysis of imaging with ℓ1 optimization
Liliana Borcea, Ilker Kocyigit
PDF: Resolution analysis of imaging with ℓ1 optimization
We study array imaging of a sparse scene of point-like sources or scatterers in a homogeneous medium. For source imaging the sensors in the array are receivers that collect measurements of the wave field. For imaging scatterers the array probes the medium with waves and records the echoes. In either case the image formation is stated as a sparsity promoting ℓ1 optimization problem, and the goal of the paper is to quantify the resolution. We consider both narrow-band and broad-band imaging, and a geometric setup with a small array. We take first the case of the unknowns lying on the imaging grid, and derive resolution limits that depend on the sparsity of the scene. Then we consider the general case with the unknowns at arbitrary locations. The analysis is based on estimates of the cumulative mutual coherence and a related concept, which we call interaction coefficient. It complements recent results in compressed sensing by deriving deterministic resolution limits that account for worse case scenarios in terms of locations of the unknowns in the imaging region, and also by interpreting the results in some cases where uniqueness of the solution does not hold. We demonstrate the theoretical predictions with numerical simulations.
Abstract. We study array imaging of a sparse scene of point-like sources or scatterers in a homogeneous medium. For source imaging the sensors in the array are receivers that collect measurements of the wave field. For imaging scatterers the array probes the medium with waves and records the echoes. In either case the image formation is stated as a sparsity promoting l1 optimization problem, and the goal of the paper is to quantify the resolution. We consider both narrow-band and broad- band imaging, and a geometric setup with a small array. We take first the case of the unknowns lying on the imaging grid, and derive resolution limits that depend on the sparsity of the scene. Then we consider the general case with the unknowns at arbitrary locations. The analysis is based on estimates of the cumulative mutual coherence and a related concept, which we call interaction coefficient. It complements recent results in compressed sensing by deriving deterministic resolution limits that account for worse case scenarios in terms of locations of the unknowns in the imaging region, and also by interpreting the results in some cases where uniqueness of the solution does not hold. We demonstrate the theoretical predictions with numerical simulations.
Key words. array imaging, sparse, l1 optimization, cumulative mutual coherence.
1. Introduction. Array imaging is an inverse problem for the wave equation, where the goal is to determine remote sources or scatterers from measurements of the wave field at a collection of nearby sensors, called the array. The problem has applications in medical imaging, nondestructive evaluation of materials, oil prospecting, seismic imaging, radar imaging, ocean acoustics and so on. There is extensive literature on various imaging approaches such as reverse time migration and its high frequency version called Kirchhoff migration [2, 3, 14], matched field imaging [1], Multiple Signal Classification (MUSIC) [30, 23], the linear sampling method [9], and the factorization method [25]. In this paper we consider array imaging using l1 optimization, which is appropriate for sparse scenes of unknown sources or scatterers that have small support in the imaging region.
Imaging with sparsity promoting optimization has received much attention recently, specially in the context of compressed sensing [21, 19, 29], where a random set of sensors collect data from a sparse scene. Such studies use the restricted isometry property of the sensing matrix [10] or its mutual coherence [8] to derive probability bounds on the event that the imaging scene is recovered exactly for noiseless data, or with small error that scales linearly with the noise level. The array does not play an essential role in these studies, aside from its aperture bounding the random sample of locations of the sensors, and for justifying the scaling that leads to models of wave propagation like the paraxial one [21].
A different approach proposed in [11, 12] images a sparse scattering scene using illuminations derived from the singular value decomposition (SVD) of the response matrix measured by probing sequentially the medium with pulses emitted by one sensor at a time and recording the echoes. Iluminations derived from the SVD are known to be useful in imaging [27, 6, 4, 5, 23] and they may mitigate noise. The setup in [11], which is typical in array imaging, lets the sensors be closely spaced so that sums over them can be approximated by integrals over the array aperture. We consider the same continuous aperture setup here and study the resolution of the images produced by l1 optimization, also known as basis pursuit and l1−penalty. We address two questions: (1) How should we chose the discretization of the imaging region so that we can guarantee unique recovery of the sparse scene, at least when the unknowns lie on the grid? (2) If the imaging region is discretized on a finer grid, for which uniqueness does not hold, are there cases where the solution of the l1 optimization is still useful?
By studying question (1) we complement the existing results with deterministic resolution limits that account for worse case scenarios, and guarantee unique recovery of the scene for a given sparsity s. This is defined as the number of non-zero entries of the vector of unknowns or, equivalently, the number of grid points in the support of the sources/scatterers that we image. We consider a geometric setup with a small array, where wave propagation can be modeled by the paraxial approximation. We have a more general paraxial model than in [21], which takes into consideration sources/scatterers at different ranges from the array. This turns out to be important in narrow-band regimes. We also consider broad-band regimes and show that the additional multi-frequency data improves the resolution.
It is typical in imaging with sparsity promoting optimization to assume that the unknown sources of scatterers lie on the discretization grid, meaning that they can be modeled by a sparse complex vector ρ ∈ CN , where N is the number of grid points. If the unknowns lie off-grid the results deteriorate. We refer to [24, 18] for a perturbation analysis of compressed sensing with small off-grid displacements. General tight error bounds can be found in [13]. They may be quite large and increase with N. Thus, there is a trade-off in imaging with l1 optimization: on one hand we need a coarse enough discretization of the imaging region to ensure unique recovery of the solution, and on the other hand finer discretization to minimize modeling errors due to off-grid placement of the unknowns. This trade-off is particularly relevant in the narrow-band paraxial regime, where the resolution limits may grow significantly with the sparsity s of the scene.
At question (2) we consider fine discretizations of the imaging region, to mitigate the modeling error. The problem is then how to interpret the result ρ⋆ of the l1 minimization, which is no longer guaranteed to be unique. We show that there are cases where the minimization may be useful. Specifically, we prove that when the unknown sources/scatterers are located at points or clusters of points that are sufficiently well separated, an l1 minimizer ρ⋆ is supported in the vicinity of these points. While the entries of ρ⋆ may not be close in the point-wise sense to those of ρ, their average over such vicinities are close to the true values in ρ in the case of well separated points, or the averages of the true values in the case of clusters of points. That is to say, l1 optimization gives an effective vector of source/scatterer amplitudes averaged locally around the points in its support. Note that question (2) was also investigated in [20], where novel algorithms for imaging well separated sources have been introduced and analyzed. Our study complements the results in [20] by analyzing directly the performance of the l1 minimization and l1-penalty, and also considering clusters of sources/scatterers.
The paper is organized as follows. In section 2 we formulate the problem, introduce notation, and describe the relation between imaging sources vs. scatterers. Question (1) is studied in section 3. We describe the paraxial scaling regime and derive resolution bounds that depend on the sparsity s of the imaging scene. In section 4 we study question (2). In both sections we begin with the statement of results and numerical illustrations, and end with the proofs. A summary is in section 5.
2. Formulation of the imaging problem. We formulate first the basic problem of imaging s point- like sources with a remote array of sensors that record the incoming sound waves. The generalization to the inverse scattering problem is described in section 2.2
arXiv:1507.00586v1 [math.NA]