The Bayesian Cramér-Rao bound (BCRB) is a crucial tool in signal processing for assessing the fundamental limitations of any estimation problem as well as benchmarking within a Bayesian frameworks. However, the BCRB cannot be computed without full knowledge of the prior and the measurement distributions. In this work, we propose a fully learned Bayesian Cramér-Rao bound (LBCRB) that learns both the prior and the measurement distributions. Specifically, we suggest two approaches to obtain the LBCRB: the Posterior Approach and the Measurement-Prior Approach. The Posterior Approach provides a simple method to obtain the LBCRB, whereas the Measurement-Prior Approach enables us to incorporate domain knowledge to improve the sample complexity and interpretability. To achieve this, we introduce a Physics-encoded score neural network which enables us to easily incorporate such domain knowledge into a neural network. We study the learning errors of the two suggested approaches theoretically, and validate them numerically. We demonstrate the two approaches on several signal processing examples, including a linear measurement problem with unknown mixing and Gaussian noise covariance matrices, frequency estimation, and quantized measurement. In addition, we test our approach on a nonlinear signal processing problem of frequency estimation with real-world underwater ambient noise.

We introduce the Generative Barankin Bound (GBB), a learned Barankin Bound, for evaluating the achievable performance in estimating the direction of arrival (DOA) of a source in non-asymptotic conditions, when the statistics of the measurement are unknown. We first learn the measurement distribution using a conditional normalizing flow (CNF) and then use it to derive the GBB. We show that the resulting learned bound approximates the analytical Barankin bound well for the case of a Gaussian signal in Gaussian noise, Then, we evaluate the GBB for cases where analytical expressions for the Barankin Bound cannot be derived. In particular, we study the effect of non-Gaussian scenarios on the threshold SNR.

The Misspecified Cramér-Rao lower bound (MCRB) provides a lower bound on the performance of any unbiased estimator of parameter vector θ under model misspecification. An approximation of the MCRB can be numerically evaluated using a set of i.i.d samples of the true distribution at θ. However, obtaining a good approximation for multiple values of θ requires collocating an unrealistically large number of samples. In this paper, we present a method for approximating the MCRB using a Generative Model, referred to as a Generative Misspecified Lower Bound (GMLB), in which we train a generative model on data from the true measurement distribution. Then, the generative model can generate as many samples as required for any θ, and therefore the GMLB can use a limited set of training data to achieve an excellent approximation of the MCRB for any parameter. We demonstrate the GMLB on two examples: a misspecified Linear Gaussian model; and a Non-Linear Truncated Gaussian model. In both cases, we empirically show the benefits of the GMLB in accuracy and sample complexity. In addition, we show the ability of the GMLB to approximate the MCRB on unseen parameters.

Dynamic tomography is an ill-posed inverse problem where the object evolves during the sequential acquisition of projections. The goal is to reconstruct the object for each time instant. However, performing a direct reconstruction using this inconsistent set of projections is impossible. In this paper, we propose an object-domain recovery algorithm using a variational formulation that combines a partially separable spatio-temporal prior with a basic total-variation spatial regularization for improved performance, while preserving full interpretability. Numerical experiments on data derived from real object CT data demonstrate the advantages of the proposed algorithm over recent projection-domain and deep-prior-based methods.

Dynamic imaging involves the recovery of a time-varying 2D or 3D object at each time instant using its undersampled measurements. In particular in dynamic tomography, only a single projection at a single view angle may be available at a time, making the problem severely ill-posed. In this work, we propose an approach, RED-PSM, which combines for the first time two powerful techniques to address this challenging imaging problem. The first, are partially separable models, which have been used to introduce a low-rank prior for the spatio-temporal object. The second is the recent Regularization by Denoising (RED), which provides a flexible framework to exploit the impressive performance of state-of-the-art image denoising algorithms, for various inverse problems. We propose a partially separable objective with RED and an optimization scheme with variable splitting and ADMM. Our objective is proved to converge to a value corresponding to a stationary point satisfying the first-order optimality conditions. Convergence is accelerated by a particular projection-domain-based initialization. We demonstrate the performance and computational improvements of our proposed RED-PSM with a learned image denoiser by comparing it to a recent deep-prior-based method TD-DIP. Although the emphasis is on dynamic tomography, we also demonstrate the performance advantages of RED-PSM in a dynamic cardiac MRI setting.

We present an algorithm for the resolution of delayed and overlapping pulses of a common unknown shape from multi-channel measurements. We show that just a few Fourier samples acquired by a Time Encoding Machine (TEM) suffice to solve this challenging problem. This acquisition scheme is desired for ultra-low power applications in wearables, such as EMG skin sensor tattoo. Numerical experiments demonstrate exact recovery of the time delays and Fourier series coefficient of the pulse shape in the noiseless case as predicted by the theory, with acceptable error in the presence of noise.

Deep-learning-based methods for various applications have been shown vulnerable to adversarial examples. Here we address the use of deep-learning networks as inverse problem solvers, which has generated much excitement and even adoption efforts by the main equipment vendors for medical imaging including computed tomography (CT) and MRI. However, the recent demonstration that such networks suffer from a similar vulnerability to adversarial attacks potentially undermines their future. We propose to modify the training strategy of end-to-end deep-learning-based inverse problem solvers to improve robustness. To this end, we introduce an auxiliary net-work to generate adversarial examples, which is used in a min-max formulation to build robust image reconstruction networks. Theoretically, we argue that for such inverse problem solvers, one should analyze and study the effect of adversaries in the measurement-space, instead of in the signal-space used in previous work. We show for a linear reconstruction scheme that our min-max formulation results in a singular-value filter regularized solution, which suppresses the effect of adversarial examples. Numerical experiments using the proposed min-max scheme confirm convergence to this solution. We complement the theory by experiments on non-linear Compressive Sensing(CS) reconstruction by a deep neural network on two standard datasets, and, using anonymized clinical data, on a state-of-the-art published algorithm for low-dose x-ray CT reconstruction. We show a significant improvement in robustness over other methods for deep network-based reconstruction, by using the proposed approach.

Recent works on adaptive sparse and on low-rank signal modeling have demonstrated their usefulness in various image/video processing applications. Patch-based methods exploit local patch sparsity, whereas other works apply low-rankness of grouped patches to exploit image non-local structures. However, using either approach alone usually limits performance in image reconstruction or recovery applications. In this work, we propose a simultaneous sparsity and low-rank model, dubbed STROLLR, to better represent natural images. In order to fully utilize both the local and non-local image properties, we develop an image restoration framework using a transform learning scheme with joint low-rank regularization. The approach owes some of its computational efficiency and good performance to the use of transform learning for adaptive sparse representation rather than the popular synthesis dictionary learning algorithms, which involve approximation of NP-hard sparse coding and expensive learning steps. We demonstrate the proposed framework in various applications to image denoising, inpainting, and compressed sensing based magnetic resonance imaging. Results show promising performance compared to state-of-the-art competing methods.

Multichannel blind deconvolution is the problem of recovering an unknown signal f and multiple unknown channels xifrom convolutional measurements yi= xi⊕ f (i = 1, 2, ..., N). We consider the case where the xi's are sparse, and convolution with f is invertible. Our nonconvex optimization formulation solves for a filter h on the unit sphere that produces sparse output yi⊕ h. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of f up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of f and xiusing a simple manifold gradient descent algorithm with random initialization. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods.

A Generative Adversarial Network (GAN) with generator G trained to model the prior of images has been shown to perform better than sparsity-based regularizers in ill-posed inverse problems. Here, we propose a new method of deploying a GAN-based prior to solve linear inverse problems using projected gradient descent (PGD). Our method learns a network-based projector for use in the PGD algorithm, eliminating expensive computation of the Jacobian of G. Experiments show that our approach provides a speed-up of 60-80x over earlier GAN-based recovery methods along with better accuracy in compressed sensing. Our main theoretical result is that if the measurement matrix is moderately conditioned on the manifold range(G) and the projector is \delta-approximate, then the algorithm is guaranteed to reach O(\delta) reconstruction error in O(log(1/\delta)) steps in the low noise regime. Additionally, we propose a fast method to design such measurement matrices for a given G. Extensive experiments demonstrate the efficacy of this method by requiring 5-10x fewer measurements than random Gaussian measurement matrices for comparable recovery performance. Because the learning of the GAN and projector is decoupled from the measurement operator, our GAN-based projector and recovery algorithm are applicable without retraining to all linear inverse problems in which the measurement operator is moderately conditioned for range(G), as confirmed by experiments on compressed sensing, super-resolution, and inpainting.

Techniques exploiting the sparsity of images in a transform domain are effective for various applications in image and video processing. In particular, transform learning methods involve cheap computations and have been demonstrated to perform well in applications, such as image denoising and medical image reconstruction. Recently, we proposed methods for online learning of sparsifying transforms from streaming signals, which enjoy good convergence guarantees and involve lower computational costs than online synthesis dictionary learning. In this paper, we apply online transform learning to video denoising. We present a novel framework for online video denoising based on high-dimensional sparsifying transform learning for spatio-temporal patches. The patches are constructed either from corresponding 2D patches in successive frames or using an online block matching technique. The proposed online video denoising requires little memory and offers efficient processing. Numerical experiments evaluate the performance of the proposed video denoising algorithms on multiple video data sets. The proposed methods outperform several related and recent techniques, including denoising with 3D DCT, prior schemes based on dictionary learning, non-local means, background separation, and deep learning, as well as the popular VBM3D and VBM4D.

Multichannel blind deconvolution is the problem of recovering an unknown signal f and multiple unknown channels xifrom their circular convolution yi= xi® f (i = 1, 2, . .., N). We consider the case where the xi's are sparse, and convolution with f is invertible. Our nonconvex optimization formulation solves for a filter h on the unit sphere that produces sparse output yi® h. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of f up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of f and xiusing a simple manifold gradient descent (MGD) algorithm. The same approach is also applicable to blind gain and phase calibration with a Fourier sensing matrix. Our algorithm and analysis require fewer assumptions than previous algorithms for the same problem. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods. Empirically, our algorithm has low computation cost (converging in a small number of iterations) and low memory footprint (solving only for the inverse filter of f ).

Blind gain and phase calibration (BGPC) is a bilinear inverse problem involving the determination of unknown gains and phases of the sensing system, and the unknown signal, jointly. BGPC arises in numerous applications, e.g., blind albedo estimation in inverse rendering, synthetic aperture radar autofocus, and sensor array auto-calibration. In some cases, sparse structure in the unknown signal alleviates the ill-posedness of BGPC. Recently, there has been renewed interest in solutions to BGPC with careful analysis of error bounds. In this paper, we formulate BGPC as an eigenvalue/eigenvector problem and propose to solve it via power iteration, or in the sparsity or joint sparsity case, via truncated power iteration. Under certain assumptions, the unknown gains, phases, and the unknown signal can be recovered simultaneously. Numerical experiments show that power iteration algorithms work not only in the regime predicted by our main results, but also in regimes where theoretical analysis is limited. We also show that our power iteration algorithms for BGPC compare favorably with competing algorithms in adversarial conditions, e.g., with noisy measurement or with a bad initial estimate.

Multichannel blind deconvolution is the problem of recovering an unknown signal $f$ and multiple unknown channels $x_i$ from convolutional measurements $y_i=x_i \circledast f$ ($i=1,2,\dots,N$). We consider the case where the $x_i$'s are sparse, and convolution with $f$ is invertible. Our nonconvex optimization formulation solves for a filter $h$ on the unit sphere that produces sparse output $y_i\circledast h$. Under some technical assumptions, we show that all local minima of the objective function correspond to the inverse filter of $f$ up to an inherent sign and shift ambiguity, and all saddle points have strictly negative curvatures. This geometric structure allows successful recovery of $f$ and $x_i$ using a simple manifold gradient descent algorithm with random initialization. Our theoretical findings are complemented by numerical experiments, which demonstrate superior performance of the proposed approach over the previous methods.

Compressed sensing of simultaneously sparse and low-rank matrices enables recovery of sparse signals from a few linear measurements of their bilinear form. One important question is how many measurements are needed for a stable reconstruction in the presence of measurement noise. Unlike conventional compressed sensing for sparse vectors, where convex relaxation via the ℓ1-norm achieves near-optimal performance, for compressed sensing of sparse low-rank matrices, it has been shown recently that convex programmings using the nuclear norm and the mixed norm are highly suboptimal even in the noise-free scenario. We propose an alternating minimization algorithm called sparse power factorization (SPF) for compressed sensing of sparse rank-one matrices. For a class of signals whose sparse representation coefficients are fast-decaying, SPF achieves stable recovery of the rank-one matrix formed by their outer product and requires number of measurements within a logarithmic factor of the information-theoretic fundamental limit. For the recovery of general sparse low-rank matrices, we propose subspace-concatenated SPF (SCSPF), which has analogous near-optimal performance guarantees to SPF in the rank-one case. Numerical results show that SPF and SCSPF empirically outperform convex programmings using the best known combinations of mixed norm and nuclear norm.

Data-driven and learning-based sparse signal models outperform analytical models (e.g, wavelets), for image denoising, but require careful parameter tuning to reach peak performance. In this work, we provide a solution to the problem of parameter tuning for image denoising with transform sparsity regularization. We show that by viewing a learned sparsifying transform as a filter bank we can utilize the SURELET denoising algorithm to automatically tune parameters for an image denoising task. Numerical experiments show that combining SURELET with a learned sparsifying transform provides the best of both worlds. Our approach requires no parameter tuning for image denoising, yet outperforms SURELET with analytic transforms and matches the performance of transform learning denoising with hand-tuned parameters.

Recent works on adaptive sparse signal modeling have demonstrated their usefulness in various image/video processing applications. As the popular synthesis dictionary learning methods involve NP-hard sparse coding and expensive learning steps, transform learning has recently received more interest for its cheap computation. However, exploiting local patch sparsity alone usually limits performance in various image processing tasks. In this work, we propose a joint adaptive patch sparse and group low-rank model, dubbed STROLLR, to better represent natural images. We develop an image restoration framework based on the proposed model, which involves a simple and efficient alternating algorithm. We demonstrate applications, including image denoising and inpainting. Results show promising performance even when compared to state-of-the-art methods.

Recent works on adaptive sparse and low-rank signal modeling have demonstrated their usefulness, especially in image/video processing applications. While a patch-based sparse model imposes local structure, low-rankness of the grouped patches exploits non-local correlation. Applying either approach alone usually limits performance in various low-level vision tasks. In this work, we propose a novel video denoising method, based on an online tensor reconstruction scheme with a joint adaptive sparse and low-rank model, dubbed SALT. An efficient and unsupervised online unitary sparsifying transform learning method is introduced to impose adaptive sparsity on the fly. We develop an efficient 3D spatio-temporal data reconstruction framework based on the proposed online learning method, which exhibits low latency and can potentially handle streaming videos. To the best of our knowledge, this is the first work that combines adaptive sparsity and low-rankness for video denoising, and the first work of solving the proposed problem in an online fashion. We demonstrate video denoising results over commonly used videos from public datasets. Numerical experiments show that the proposed video denoising method outperforms competing methods.

Subsampled blind deconvolution is the recovery of two unknown signals from samples of their convolution. To overcome the ill-posedness of this problem, solutions based on priors tailored to specific practical application have been developed. In particular, sparsity models have provided promising priors. However, in spite of the empirical success of these methods in many applications, existing analyses are rather limited in two main ways: by disparity between the theoretical assumptions on the signal and/or measurement model versus practical setups; or by failure to provide a performance guarantee for parameter values within the optimal regime defined by the information theoretic limits. In particular, it has been shown that a naive sparsity model is not a strong enough prior for identifiability in the blind deconvolution problem. Instead, in addition to sparsity, we adopt a conic constraint, which enforces spectral flatness of the signals. Under this prior together with random dictionary models, we show that the unknown sparse signals can be recovered from samples of their convolution at a rate scaling near optimally with the problem parameters. We also propose an iterative algorithm that is guaranteed to provide robust recovery at the same near optimal sample complexity provided that certain projection steps in the algorithm are successful. In our analysis, we have not verified the success of these projection steps, but these steps are inactive with high probability. Numerical results show the empirical performance of the iterative algorithm agrees with the performance guarantee.

Bilinear inverse problems (BIPs), the resolution of two vectors given their image under a bilinear mapping, arise in many applications. Without further constraints, BIPs are usually ill-posed. In practice, the properties of natural signals are exploited to solve BIPs. For example, subspace constraints or sparsity constraints are imposed to reduce the search space. These approaches have shown some success in practice. However, there are few results on uniqueness in BIPs. For most BIPs, the fundamental question of under what condition the problem admits a unique solution is yet to be answered. For example, blind gain and phase calibration (BGPC) is a structured BIP, which arises in many applications, including inverse rendering in computational relighting (albedo estimation with unknown lighting), blind phase and gain calibration in sensor array processing, and multichannel blind deconvolution (MBD). It is interesting to study the uniqueness of such problems. In this paper, we define identifiability of a BIP up to a group of transformations. We derive necessary and sufficient conditions for such identifiability, i.e., the conditions under which the solutions can be uniquely determined up to the transformation group. These conditions take the form of dividing the identifiability of the pair of unknown variables into the individual identifiability of each variable. Although verifying these individual conditions requires problem-specific procedures, this framework is universally applicable to all BIPs. Applying these results to BGPC, we derive sufficient conditions for unique recovery under several scenarios, including subspace, joint sparsity, and sparsity models. For BGPC with joint sparsity or sparsity constraints, we develop a procedure to compute the transformation groups corresponding to inherent ambiguities. We also give necessary conditions in the form of tight lower bounds on sample complexities, and demonstrate the tightness of these bounds by numerical experiments. The results for BGPC not only demonstrate the application of the proposed general framework for identifiability analysis, but are also of interest in their own right.

Blind deconvolution (BD) arises in many applications. Without assumptions on the signal and the filter, BD does not admit a unique solution. In practice, subspace or sparsity assumptions have shown the ability to reduce the search space and yield the unique solution. However, existing theoretical analysis on uniqueness in BD is rather limited. In an earlier paper, we provided the first algebraic sample complexities for BD that hold for Lebesgue almost all bases or frames. We showed that for BD of a pair of vectors in ℂn, with subspace constraints of dimensions m1and m2, respectively, a sample complexity of n ≥ m1m2is sufficient. This result is suboptimal, since the number of degrees of freedom is merely m1+ m2- 1. We provided analogous results, with similar suboptimality, for BD with sparsity or mixed subspace and sparsity constraints. In this paper, taking advantage of the recent progress on the information-theoretic limits of unique low-rank matrix recovery, we finally bridge this gap, and derive an optimal sample complexity result for BD with generic bases or frames. We show that for BD of an arbitrary pair (respectively, all pairs) of vectors in ℂn, with sparsity constraints of sparsity levels s1 and s2, a sample complexity of n > s1+ s2[respectively, n > 2(s1+s2)] is sufficient. We also present analogous results for BD with subspace constraints or mixed constraints, with the subspace dimension replacing the sparsity level. Last but not least, in all the above scenarios, if the bases or frames follow a probabilistic distribution specified in this paper, the recovery is not only unique, but also stable against small perturbations in the measurements, under the same sample complexities.

Adaptive sparse representation has been heavily exploited in signal processing and computer vision. Recently, sparsifying transform learning received interest for its cheap computation and optimal updates in the alternating algorithms. In this work, we develop a methodology for learning a Flipping and Rotation Invariant Sparsifying Transform, dubbed FRIST, to better represent natural images that contain textures with various geometrical directions. The proposed alternating learning algorithm involves efficient optimal updates. We demonstrate empirical convergence behavior of the proposed learning algorithm. Preliminary experiments show the usefulness of FRIST for image sparse representation, segmentation, robust inpainting, and MRI reconstruction with promising performances.

Tremendous efforts have been made to study the theoretical and algorithmic aspects of sparse recovery and low-rank matrix recovery. This paper establishes (near) optimal sample complexities for stable matrix recovery without constants or log factors. We treat sparsity, low-rankness, and other parsimonious structures within the same framework: constraint sets that have small covering numbers or Minkowski dimensions, which include notoriously challenging cases such as simultaneously sparse and low-rank matrices. We consider three types of random measurement matrices (unstructured, rank-1, and symmetric rank-1 matrices), following probability distributions that satisfy some mild conditions. In all these cases, we prove a fundamental achievability result - the recovery of matrices with parsimonious structures, using an optimal (or near optimal) number of measurements, is stable with high probability.

Blind deconvolution (BD), the resolution of a signal and a filter given their convolution, arises in many applications. Without further constraints, BD is ill-posed. In practice, subspace or sparsity constraints have been imposed to reduce the search space, and have shown some empirical success. However, the existing theoretical analysis on uniqueness in BD is rather limited. In an effort to address the still open question, we derive sufficient conditions under which two vectors can be uniquely identified from their circular convolution, subject to subspace or sparsity constraints. These sufficient conditions provide the first algebraic sample complexities for BD. We first derive a sufficient condition that applies to almost all bases or frames. For BD of vectors in ℂn, with two subspace constraints of dimensions m1and m2, the required sample complexity is n ≥ m1m2. Then, we impose a sub-band structure on one basis, and derive a sufficient condition that involves a relaxed sample complexity n≥ m1+m2-1, which we show to be optimal. We present the extensions of these results to BD with sparsity constraints or mixed constraints, with the sparsity level replacing the subspace dimension. The cost for the unknown support in this case is an extra factor of 2 in the sample complexity.

Exploiting the sparsity of signals in an adaptive dictionary or transform domain benefits various applications in image/video processing. As opposed to synthesis dictionary learning, transform learning allows for cheap computations, and has been demonstrated to perform well in applications such as image denoising. Very recently, we proposed methods for online sparsifying transform learning, which are particularly useful for processing large-scale or streaming data. Online transform learning has good convergence guarantees and enjoys a much lower computational cost than online synthesis dictionary learning. In this work, we present a video denoising framework based on online 3D spatio-temporal sparsifying transform learning. The proposed scheme has low computational and memory costs, and can potentially handle streaming video. Our numerical experiments show promising performance for the proposed video denoising method compared to popular prior or state-of-the-art methods.

Natural signals and images are well known to be approximately sparse in transform domains such as wavelets and discrete cosine transform. This property has been heavily exploited in various applications in image processing and medical imaging. Compressed sensing exploits the sparsity of images or image patches in a transform domain or synthesis dictionary to reconstruct images from undersampled measurements. In this work, we focus on blind compressed sensing, where the underlying sparsifying transform is a priori unknown, and propose a framework to simultaneously reconstruct the underlying image as well as the sparsifying transform from highly undersampled measurements. The proposed block coordinate descent-type algorithms involve highly efficient optimal updates. Importantly, we prove that although the proposed blind compressed sensing formulations are highly nonconvex, our algorithms are globally convergent (i.e., they converge from any initialization) to the set of critical points of the objectives defining the formulations. These critical points are guaranteed to be at least partial global and partial local minimizers. The exact point(s) of convergence may depend on initialization. We illustrate the usefulness of the proposed framework for magnetic resonance image reconstruction from highly undersampled k-space measurements. As compared to previous methods involving the synthesis dictionary model, our approach is much faster, while also providing promising reconstruction quality.

A central problem in computed tomography (CT) imaging is to obtain useful, high-quality images from low-dose measurements. Methods that exploit the sparse representations of tomographic images have long been known to improve the quality of reconstructions from low-dose data. Recent work has shown that sparse representations learned directly from the data can outperform traditional, fixed representations, but are prohibitively expensive for practical use in CT. We propose a new method for tomographic reconstruction from low-dose data by combining the statistically weighted data fidelity term with an adaptive sparsifying transform regularizer. This regularizer can be fit to the data at lower cost than competing methods. Our algorithm alternates between reconstructing the image and learning the sparsifying transform. The Alternating Direction Method of Multipliers technique is used to provide an efficient solution to the statistically weighted minimization problem. Numerical experiments on data from clinical CT reconstructions indicate that adaptive sparsifying transform regularization outperforms synthesis sparsity methods at speeds rivaling total-variation regularization.

The sparsity of natural signals in transform domains such as the DCT has been heavily exploited in various applications. Recently, we introduced the idea of learning sparsifying transforms from data, and demonstrated the usefulness of learnt transforms in image representation, and denoising. However, the learning formulations therein were non-convex, and the algorithms lacked strong convergence properties. In this work, we propose a novel convex formulation for square sparsifying transform learning. We also enforce a doubly sparse structure on the transform, which makes its learning, storage, and implementation efficient. Our algorithm is guaranteed to converge to a global optimum, and moreover converges quickly. We also introduce a non-convex variant of the convex formulation, for which the algorithm is locally convergent. We show the superior promise of our learnt transforms as compared to analytical sparsifying transforms such as the DCT for image representation.

The sparsity of images in a transform domain or dictionary has been widely exploited in image processing. Compared to the synthesis dictionary model, sparse coding in the (single) transform model is cheap. However, natural images typically contain diverse textures that cannot be sparsified well by a single transform. Hence, we propose a union of sparsifying transforms model, which is equivalent to an overcomplete transform model with block cosparsity (OC-TOBOS). Our alternating algorithm for transform learning involves simple closed-form updates. When applied to images, our algorithm learns a collection of well-conditioned transforms, and a good clustering of the patches or textures. Our learnt transforms provide better image representations than learned square transforms. We also show the promising denoising performance and speedups provided by the proposed method compared to synthesis dictionary-based denoising.

One of the technical challenges in cine magnetic resonance imaging (MRI) is to reduce the acquisition time to enable the high spatio-temporal resolution imaging of a cardiac volume within a short scan time. Recently, compressed sensing approaches have been investigated extensively for highly accelerated cine MRI by exploiting transform domain sparsity using linear transforms such as wavelets, and Fourier. However, in cardiac cine imaging, the cardiac volume changes significantly between frames, and there often exist abrupt pixel value changes along time. In order to effectively sparsify such temporal variations, it is necessary to exploit temporal redundancy along motion trajectories. This paper introduces a novel patch-based reconstruction method to exploit geometric similarities in the spatio-temporal domain. In particular, we use a low rank constraint for similar patches along motion, based on the observation that rank structures are relatively less sensitive to global intensity changes, but make it easier to capture moving edges. A Nash equilibrium formulation with relaxation is employed to guarantee convergence. Experimental results show that the proposed algorithm clearly reconstructs important anatomical structures in cardiac cine image and provides improved image quality compared to existing state-of-the-art methods such as k-t FOCUSS, k-t SLR, and MASTeR.

Adaptive sparse representations have been very popular in numerous applications in recent years. The learning of synthesis sparsifying dictionaries has particularly received much attention, and such adaptive dictionaries have been shown to be useful in applications such as image denoising, and magnetic resonance image reconstruction. In this work, we focus on the alternative sparsifying transform model, for which sparse coding is cheap and exact, and study the learning of tall or overcomplete sparsifying transforms from data. We propose various penalties that control the sparsifying ability, condition number, and incoherence of the learnt transforms. Our alternating algorithm for transform learning converges empirically, and significantly improves the quality of the learnt transform over the iterations. We present examples demonstrating the promising performance of adaptive overcomplete transforms over adaptive overcomplete synthesis dictionaries learnt using K-SVD, in the application of image denoising.

Many applications in signal processing benefit from the sparsity of signals in a certain transform domain or dictionary. Synthesis sparsifying dictionaries that are directly adapted to data have been popular in applications such as image denoising, and medical image reconstruction. In this work, we focus specifically on the learning of orthonormal as well as well-conditioned square sparsifying transforms. The proposed algorithms alternate between a sparse coding step, and a transform update step. We derive the exact analytical solution for each of these steps. Adaptive well-conditioned transforms are shown to perform better in applications compared to adapted orthonormal ones. Moreover, the closed form solution for the transform update step achieves the global minimum in that step, and also provides speedups over iterative solutions involving conjugate gradients. We also present examples illustrating the promising performance and significant speed-ups of transform learning over synthesis K-SVD in image denoising.

The multiple measurement vector problem (MMV) is a generalization of the compressed sensing problem that addresses the recovery of a set of jointly sparse signal vectors. One of the important contributions of this paper is to reveal that the seemingly least related state-of-art MMV joint sparse recovery algorithms - M-SBL (multiple sparse Bayesian learning) and subspace-based hybrid greedy algorithms - have a very important link. More specifically, we show that replacing the log det(·) term in M-SBL by a log det(·) rank proxy that exploits the spark reduction property discovered in subspace-based joint sparse recovery algorithms, provides significant improvements. Theoretical analysis demonstrates that even thoughM-SBL is often unable to remove all localminimizers, the proposed method can do so under fairly mild conditions, without affecting the global minimizer.

Compressed sensing enables universal, simple, and reduced-cost acquisition by exploiting a sparse signal model. Most notably, recovery of the signal by computationally efficient algorithms is guaranteed for certain random measurement models, which satisfy the so-called isotropy property. However, in real-world applications, this property is often not satisfied. We propose two related changes in the existing framework for the anisotropic case: (i) a generalized RIP called the restricted biorthogonality property (RBOP); and (ii) correspondingly modified versions of existing greedy pursuit algorithms, which we call oblique pursuits. Oblique pursuits provide recovery guarantees via the RBOP without requiring the isotropy property; hence, these recovery guarantees apply to practical acquisition schemes. Numerical results show that oblique pursuits also perform better than their conventional counterparts.

The sparsity of images in a transform domain or dictionary has been exploited in many applications in image processing. For example, analytical sparsifying transforms, such as wavelets and discrete cosine transform (DCT), have been extensively used in compression standards. Recently, synthesis sparsifying dictionaries that are directly adapted to the data have become popular especially in applications such as image denoising. Following up on our recent research, where we introduced the idea of learning square sparsifying transforms, we propose here novel problem formulations for learning doubly sparse transforms for signals or image patches. These transforms are a product of a fixed, fast analytic transform such as the DCT, and an adaptive matrix constrained to be sparse. Such transforms can be learnt, stored, and implemented efficiently. We show the superior promise of our learnt transforms as compared with analytical sparsifying transforms such as the DCT for image representation. We also show promising performance in image denoising that compares favorably with approaches involving learnt synthesis dictionaries such as the K-SVD algorithm. The proposed approach is also much faster than K-SVD denoising.

In this correspondence, a corrected version of the convergence analysis given by Lee and Bresler in the above titled paper (ibid., vol. 56, no. 9, pp. 4402-4416, Sep. 2010) is presented.

Compressed sensing is a new data acquisition paradigm enabling universal, simple, and reduced-cost acquisition, by exploiting a sparse signal model. Most notably, recovery of the signal by computationally efficient algorithms is guaranteed for certain randomized acquisition systems. However, there is a discrepancy between the theoretical guarantees and practical applications. In applications, including Fourier imaging in various modalities, the measurements are acquired by inner products with vectors selected randomly (sampled) from a frame. Currently available guarantees are derived using the so-called restricted isometry property (RIP), which has only been shown to hold under ideal assumptions. For example, the sampling from the frame needs to be independent and identically distributed with the uniform distribution, and the frame must be tight. In practice though, one or more of the ideal assumptions are typically violated and none of the RIP-based guarantees applies. Motivated by this discrepancy, we propose two related changes in the existing framework: 1) a generalized RIP called the restricted biorthogonality property (RBOP); and 2) correspondingly modified versions of existing greedy pursuit algorithms, which we call oblique pursuits. Oblique pursuits are guaranteed using the RBOP without requiring ideal assumptions; hence, the guarantees apply to practical acquisition schemes. Numerical results show that oblique pursuits also perform competitively with, or sometimes better than their conventional counterparts.

The sparsity of signals and images in a certain analytically defined transform domain or dictionary such as discrete cosine transform or wavelets has been exploited in many applications in signal and image processing. Recently, the idea of learning a dictionary for sparse representation of data has become popular. However, while there has been extensive research on learning synthesis dictionaries, the idea of learning analysis sparsifying transforms has received only little attention. We propose a novel problem formulation and an alternating algorithm for learning well-conditioned square sparsifying transforms from data. We show the superiority of our approach for image representation over analytical sparsifying transforms such as the DCT. We also show promise in image denoising. Denoising using the learnt analysis transforms is not only better than by synthesis dictionaries learnt using the K-SVD algorithm but also faster.

The sparsity of images in a fixed analytic transform domain or dictionary such as DCT or Wavelets has been exploited in many applications in image processing including image compression. Recently, synthesis sparsifying dictionaries that are directly adapted to the data have become popular in image processing. However, the idea of learning sparsifying transforms has received only little attention. We propose a novel problem formulation for learning doubly sparse transforms for signals or image patches. These transforms are a product of a fixed, fast analytic transform such as the DCT, and an adaptive matrix constrained to be sparse. Such transforms can be learnt, stored, and implemented efficiently. We show the superior promise of our approach as compared to analytical sparsifying transforms such as DCT for image representation.

We propose robust and efficient algorithms for the joint sparse recovery problem in compressed sensing, which simultaneously recover the supports of jointly sparse signals from their multiple measurement vectors obtained through a common sensing matrix. In a favorable situation, the unknown matrix, which consists of the jointly sparse signals, has linearly independent nonzero rows. In this case, the MUltiple SIgnal Classification (MUSIC) algorithm, originally proposed by Schmidt for the direction of arrival estimation problem in sensor array processing and later proposed and analyzed for joint sparse recovery by Feng and Bresler, provides a guarantee with the minimum number of measurements. We focus instead on the unfavorable but practically significant case of rank defect or ill-conditioning. This situation arises with a limited number of measurement vectors, or with highly correlated signal components. In this case, MUSIC fails and, in practice, none of the existing methods can consistently approach the fundamental limit. We propose subspace-augmented MUSIC (SA-MUSIC), which improves on MUSIC such that the support is reliably recovered under such unfavorable conditions. Combined with a subspace-based greedy algorithm, known as Orthogonal Subspace Matching Pursuit, which is also proposed and analyzed in this paper, SA-MUSIC provides a computationally efficient algorithm with a performance guarantee. The performance guarantees are given in terms of a version of the restricted isometry property. In particular, we also present a non-asymptotic perturbation analysis of the signal subspace estimation step, which has been missing in the previous studies of MUSIC.

Diffuse optical tomography (DOT) is a sensitive and relatively low cost imaging modality that reconstructs optical properties of a highly scattering medium. However, due to the diffusive nature of light propagation, the problem is severely ill-conditioned and highly nonlinear. Even though nonlinear iterative methods have been commonly used, they are computationally expensive especially for three dimensional imaging geometry. Recently, compressed sensing theory has provided a systematic understanding of high resolution reconstruction of sparse objects in many imaging problems; hence, the goal of this paper is to extend the theory to the diffuse optical tomography problem. The main contributions of this paper are to formulate the imaging problem as a joint sparse recovery problem in a compressive sensing framework and to propose a novel noniterative and exact inversion algorithm that achieves the l(0) optimality as the rank of measurement increases to the unknown sparsity level. The algorithm is based on the recently discovered generalized MUSIC criterion, which exploits the advantages of both compressive sensing and array signal processing. A theoretical criterion for optimizing the imaging geometry is provided, and simulation results confirm that the new algorithm outperforms the existing algorithms and reliably reconstructs the optical inhomogeneities when we assume that the optical background is known to a reasonable accuracy.

Compressed sensing (CS) utilizes the sparsity of magnetic resonance (MR) images to enable accurate reconstruction from undersampled k-space data. Recent CS methods have employed analytical sparsifying transforms such as wavelets, curvelets, and finite differences. In this paper, we propose a novel framework for adaptively learning the sparsifying transform (dictionary), and reconstructing the image simultaneously from highly undersampled k-space data. The sparsity in this framework is enforced on overlapping image patches emphasizing local structure. Moreover, the dictionary is adapted to the particular image instance thereby favoring better sparsities and consequently much higher undersampling rates. The proposed alternating reconstruction algorithm learns the sparsifying dictionary, and uses it to remove aliasing and noise in one step, and subsequently restores and fills-in the k-space data in the other step. Numerical experiments are conducted on MR images and on real MR data of several anatomies with a variety of sampling schemes. The results demonstrate dramatic improvements on the order of 4-18 dB in reconstruction error and doubling of the acceptable undersampling factor using the proposed adaptive dictionary as compared to previous CS methods. These improvements persist over a wide range of practical data signal-to-noise ratios, without any parameter tuning.

Compressive sensing (CS) has seen impressive successes and fast growth over the past ten years, including applications in medical imaging. Applications of CS to magnetic resonance imaging (MRI) have been the earliest, most numerous, and most diverse, owing to the tremendous flexibility in designing the acquisition process and the pressing need that MRI has, as a slow acquisition modality, to reduce the sampling requirements.

In this paper, we address compressed sensing of a low-rank matrix posing the inverse problem as an approximation problem with a specified target rank of the solution. A simple search over the target rank then provides the minimum rank solution satisfying a prescribed data approximation bound. We propose an atomic decomposition providing an analogy between parsimonious representations of a sparse vector and a low-rank matrix and extending efficient greedy algorithms from the vector to the matrix case. In particular, we propose an efficient and guaranteed algorithm named atomic decomposition for minimum rank approximation (ADMiRA) that extends Needell and Tropp's compressive sampling matching pursuit (CoSaMP) algorithm from the sparse vector to the low-rank matrix case. The performance guarantee is given in terms of the rank-restricted isometry property (R-RIP) and bounds both the number of iterations and the error in the approximate solution for the general case of noisy measurements and approximately low-rank solution. With a sparse measurement operator as in the matrix completion problem, the computation in ADMiRA is linear in the number of measurements. Numerical experiments for the matrix completion problem show that, although the R-RIP is not satisfied in this case, ADMiRA is a competitive algorithm for matrix completion.

Recht, Fazel, and Parrilo provided an analogy between rank minimization and ¿0-norm minimization. Subject to the rank-restricted isometry property, nuclear norm minimization is a guaranteed algorithm for rank minimization. The resulting semidefinite formulation is a convex problem but in practice the algorithms for it do not scale well to large instances. Instead, we explore missing terms in the analogy and propose a new algorithm which is computationally efficient and also has a performance guarantee. The algorithm is based on the atomic decomposition of the matrix variable and extends the idea in the CoSaMP algorithm for ¿0-norm minimization. Combined with the recent fast low rank approximation of matrices based on randomization, the proposed algorithm can efficiently handle large scale rank minimization problems.

There are various conditions on the CS matrix for unique and stable recovery. These include universality, or spark, and UUP. Furthermore, quantitative bounds on the stability depend on related properties of the CS matrix. The construction of good CS matrices - satisfying the various properties - is key to successful practical applications of compressive sensing. Unfortunately, verifying the satisfiability of any of these properties for a given CS matrix involves infeasible combinatorial search. Our methods use i\ and semidefinite relaxation into a convex problem. Given a set of candidate CS matrices, our approach provides tools for the selection of good CS matrices with verified and quantitatively favorable performance.

We present upper bounds on the 2-norm of the aliasing error in multidimensional Shannon sampling. Our bounds complement the previously known 1-norm upper bounds for the peak aliasing error. The proposed bounds provide a good estimate of the total error energy for any signal, rather than just for certain pathological extremals, as is the case with the 1-norm bounds which, as a result, tend to be too conservative for practical applications. The sampling representation is general, possibly multiband, and not restricted to bandlimited signals. Error bounds are phrased in terms of the energy of signal components that lie outside the assumed band-region. Therefore, they are easy to interpret and compute as is demonstrated for two practical signal classes, namely signals with exponential or polynomial out-of-band decay.

We introduce a family of fast algorithms for 2-D parallel-beam tomographic backprojection. They aggregate the projections in a hierarchical structure involving the shearing and addition of sparsely sampled images. The algorithms achieve a computational cost of O(N(2) log P), when backprojecting an N x N pixel image from P projections. The algorithms provide a systematic means, guided by a Fourier-domain interpretation, to adjust and optimize the tradeoff between computational cost and accuracy. In an example with N = 512 and P = 1458 the algorithms provide high accuracy, with more than an order of magnitude reduction in operation counts.

This paper derives fundamental performance bounds for statistical estimation of parametric surfaces embedded in R3. Unlike conventional pixel-based image reconstruction approaches, our problem is reconstruction of the shape of binary or homogeneous objects. The fundamental uncertainty of such estimation problems can be represented by global confidenceregions, which facilitate geometric inference and optimization ofthe imaging system. Compared to our previous work on global confidence region analysis for curves [two-dimensional (2-D) shapes], computation of the probability that the entire surface estimate lies within the confidence region is more challenging because a surface estimate is an inhomogeneous random field continuously indexed by a 2-D variable. We derive an asymptotic lower bound to this probability by relating it to the exceedence probability of a higher dimensional Gaussian random field, which can, in turn, be evaluated using the tube formula due to Sun. Simulation results demonstrate the tightness of the resulting bound and the usefulness of the three-dimensional global confidence region approach.

Suffix sorting requires ordering all suffixes of all symbols in an input sequence and has applications in running queries on large texts and in universal lossless data compression based on the Burrows Wheeler transform (BWT). We propose a new suffix lists data structure that leads to three fast, antisequential, and memory-efficient algorithms for suffix sorting. For a length-N input over a size-|X| alphabet, the worst-case complexities of these algorithms are /spl Theta/(N/sup 2/), O(|X|N log(N/|X|)), and O(N/spl radic/|X|log(N/|X|)), respectively. Furthermore, simulation results indicate performance that is competitive with other suffix sorting methods. In contrast, the suffix sorting methods that are fastest on standard test corpora have poor worst-case performance. Therefore, in comparison with other suffix sorting methods, suffix lists offer a useful trade off between practical performance and worst-case behavior. Another distinguishing feature of suffix lists is that these algorithms are simple; some of them can be implemented in VLSI. This could accelerate suffix sorting by at least an order of magnitude and enable high-speed BWT-based compression systems.

We provide an O(N) algorithm for a nonsequential semipredictive encoder whose pointwise redundancy with respect to any (unbounded depth) tree source is O(1) bits per state above Rissanen's lower bound. This is achieved by using the Burrows-Wheeler transform (BWT), an invertible permutation transform that has been suggested for lossless data compression. First, we use the BWT only as an efficient computational tool for pruning context trees, and encode the input sequence rather than the BWT output. Second, we estimate the minimum description length (MDL) source by incorporating suffix tree methods to construct the unbounded depth context tree that corresponds to the input sequence in O(N) time. Third, we point out that a variety of previous source coding methods required superlinear complexity for determining which tree source state generated each of the symbols of the input. We show how backtracking from the BWT output to the input sequence enables to solve this problem in O(N) worst case complexity.

We consider the problem of multiple-input multiple-output (MIMO) sampling of multiband signals. In this problem, a set of input signals is passed through a MIMO channel modeled as a known linear time-invariant system. The inputs are modeled as multiband signals whose spectral supports are sets of finite measure and the channel outputs are sampled on nonuniform sampling sets. The aim is to reconstruct the inputs from the output samples. This sampling scheme is quite general and it encompasses various others including Papoulis' generalized sampling and nonuniform sampling as special cases. We introduce notions of joint upper and lower densities for collections of sampling sets and then derive necessary conditions on these densities for stable sampling and consistent reconstruction of the channel inputs from the sampled outputs. These results generalize classical density results for stable sampling and interpolation due to Landau.

Parallel MR imaging methods like SMASH, SENSE etc. use multiple receiver coils to accelerate the imaging process by reducing the Fourier space sampling requirement. In this paper we show how one can optimally select the sampling locations based upon (1) knowledge of the statistics of the object being imaged and, (2) a statistical criterion for optimality determined by the application. In particular we show that the optimal uniform sample spacing is not necessarily an integer multiple of the Nyquist interval and depends upon the specific coil sensitivities and configuration.

Existing algorithms for exact helical cone beam (HCB) tomographic reconstruction are computationally infeasible for clinical applications. Their computational cost is dominated by 3-D backprojection, which is generally an O(N/sup 4/) operation. We present a fast hierarchical 3-D backprojection algorithm, generalizing fast 2-D parallel beam and fan beam algorithms, which reduces the overall complexity of this step to O(N/sup 3/ log N), greatly accelerating the reconstruction.

We propose a new fast Feldkamp algorithm for 3-D cone beam tomography with a circular source trajectory. The algorithm is an extension of our recent fast native 2-D fan-beam reconstruction algorithm. It is based on a recursive hierarchical decomposition of the cone-beam backprojection operation into successively smaller sub-volumes. The algorithm reduces the computational complexity of the reconstruction from O(N/sup 4/) to O(N/sup 3/ log N). Simulations demonstrate the efficiency of our algorithm, with 7-fold speedup for a 128 /spl times/ 128 /spl times/ 128 image. Speedups will be much greater for images of more typical size encountered in medicine.

We address the problem of computing fundamental performance bounds for estimation of object boundaries from noisy measurements in inverse problems, when the boundaries are parameterized by a finite number of unknown variables. Our model applies to multiple unknown objects, each with its own unknown gray level, or color, and boundary parameterization, on an arbitrary known background. While such fundamental bounds on the performance of shape estimation algorithms can in principle be derived from the Cramér-Rao lower bounds, very few results have been reported due to the difficulty of computing the derivatives of a functional with respect to shape deformation. We provide a general formula for computing Cramér-Rao lower bounds in inverse problems where the observations are related to the object by a general linear transform, followed by a possibly nonlinear and noisy measurement system. As an illustration, we derive explicit formulas for computed tomography, Fourier imaging, and deconvolution problems. The bounds reveal that highly accurate parametric reconstructions are possible in these examples, using severely limited and noisy data.

We consider the estimation of an unknown arbitrary 2D object shape from sparse noisy samples of its Fourier transform. The estimate of the closed boundary curve is parametrized by normalized Fourier descriptors (FDs). We use Rissanen's (1998) MDL criterion. to regularize this ill-posed non-linear inverse problem and determine an optimum tradeoff between approximation and estimation errors by picking an optimum order for the FD parametrization. The performance of the proposed estimator is quantified in terms of the area discrepancy between the true and estimated object. Numerical results demonstrate the effectiveness of the proposed approach.

We address the problem of computing fundamental performance bounds for estimation of object boundaries from noisy measurements in inverse problems, when the boundaries are parameterized by a finite number of unknown variables. Our model applies to multiple unknown objects, each with its own unknown gray level, or color, and boundary parameterization, on an arbitrary known background. While such fundamental bounds on the performance of shape estimation algorithms can in principle be derived from the Cramer-Rao lower bounds, very few results have been reported due to the difficulty of computing the derivatives of a functional with respect to shape deformation. We provide a general formula for computing Cramer-Rao lower bounds in inverse problems where the observations are related to the object by a general linear transform, followed by a possibly nonlinear and noisy measurement system.

We present a novel backprojection algorithm for three-dimensional (3-D) radon transform data that requires O(N3 log2 N) operations for reconstruction of an N x N x N volume from O(N2) plane-integral projections. Our algorithm uses a hierarchical decomposition of the 3-D radon transform to recursively decompose the backprojection operation. Simulations are presented demonstrating reconstruction quality comparable to the standard filtered backprojection, which requires O(N5) computations under the same circumstances.

We propose a new impedance imaging method, electromagnetic impedance tomography (EMIT), in which the boundary electric potential measurements in electrical impedance tomography (EIT) are augmented by measurements of the exterior magnetic field induced by the currents excited in the object by the standard EIT procedures. These magnetic measurements can be obtained reliably and inexpensively by simple pickup coils located around the imaged cross section. We derive expressions for the forward problem and for the Jacobian of the measurements, and propose an iterative reconstruction algorithm using a squared error cost function. The performance of EMIT and EIT is compared in numerical simulations using a finite-element model for the conductivity distribution of several phantoms. Evaluation of the rank and condition of the Jacobian demonstrates that the additional magnetic measurements provided by a few pickup coils in EMIT turn an underdetermined EIT problem into a well-posed one with reasonable condition, or significantly improve the conditioning of the EIT problem when it is already fully determined. Reconstructions of various phantoms reveal that EMIT provides particularly significant visual and quantitative improvement (threefold to tenfold reduction in the root-mean-squared error) in the sensitivity at the center of the object, which is the area most difficult to image using EIT.

We address image estimation from sparse Fourier samples. The problem is formulated as joint estimation of the supports of unknown sparse objects in the image, and pixel values on these supports. The domain and the pixel values are alternately estimated using the level-set method and the conjugate gradient method, respectively. Our level-set evolution shows a unique switching behavior, which stabilizes the level-set evolution and removes the re-initialization steps in conventional level set approaches.

We recently proposed a novel fast backprojection algorithm for reconstruction of an N x N pixel object from O(N) projections in O(N(2)log(2)N) operations. In this paper, we analyze a simplified version of that algorithm, to determine the effects of various parameter choices on the algorithm's theoretical performance. We derive a bound on the variance of the per-pixel error introduced by using hierarchical backprojection. This bound is with respect to an ensemble of input sinograms, and allows us to construct confidence intervals (for any specified level) for the per-pixel errors. The bound has a simple form, and we show how to use it to select algorithm parameters for different cost versus error tradeoffs. Simulation results show that the bound accurately predicts the performance of the algorithm over a wide range of parameter choices. These results are verified for different images, including a tomographic reconstruction from the visual human dataset (VHD). The analysis therefore provides an effective tool for the selection of parameters and operating point for the fast hierarchical backprojection algorithm.

It is known that in the absence of distortion, the necessary sampling density for a multiband signal is given by its spectral occupancy. However, in general, the samples have to be acquired nonuniformly. There exist sampling patterns such that reconstruction is feasible even if the actual spectral support of the multiband signal is not known. If the samples are distorted, an increased sampling density may lead to a superior performance. In this paper, we consider the case of small distortion due to fine quantization of the samples, and we derive a necessary condition on the optimal sampling density.

We introduce confidence region techniques for analyzing and visualizing the performance of two-dimensional parametric shape estimators. Assuming an asymptotically normal and efficient estimator for a finite parameterization of the object boundary, Cramer-Rao bounds are used to define a confidence region, centered around the true boundary. Computation of the probability that an entire boundary estimate lies within the confidence region is a challenging problem, because the estimate is a two-dimensional nonstationary random process. We derive lower bounds on this probability using level crossing statistics. The results make it possible to generate confidence regions for arbitrary prescribed probabilities. These global confidence regions conveniently display the uncertainty in various geometric parameters such as shape, size, orientation, and position of the estimated object, and facilitate geometric inferences. Numerical simulations suggest that the new bounds are quite tight.

A novel algorithm for fast computation of tomographic image projections is presented. The method comprises a decomposition of an image into sub-images followed by an aggregation of projections computed for the sub-images. The multilevel domain decomposition algorithm is formulated as a recursive procedure. The computational cost of the proposed algorithm is comparable to that of FFT-based techniques but it provides better accuracy and more flexibility.

In the standard two-dimensional (2-D) parallel beam tomographic formulation, it is assumed that the angles at which the projections were acquired are known. In certain situations, however, these angles are known only approximately (as in the case of magnetic resonance imaging (MRI) of a moving patient), or are completely unknown. The latter occurs in a three-dimensional (3-D) version of the problem in the electron microscopy-based imaging of viral particles. We address the problem of determining the view angles directly from the projection data itself in the 2-D parallel beam case. We prove the surprising result that under some fairly mild conditions, the view angles are uniquely determined by the projection data. We present conditions for the unique recovery of these view angles based on the Helgasson-Ludwig consistency conditions for the Radon transform, we also show that when the projections are shifted by some random amount which must be jointly estimated with the view angles, unique recovery of both the shifts and view angles is possible.

In the standard two-dimensional (2-D) parallel beam tomographic formulation, it is generally assumed that the angles at which the projections were acquired are known. We have previously demonstrated, however, that under fairly mild conditions these view angles can be uniquely recovered from the projections themselves. We address the question of reliability of such solutions to the angle recovery problem using moments of the projections. We demonstrate that under mild conditions, the angle recovery problem has unique solutions and is stable with respect to perturbations in the data. Furthermore, we determine the Cramer-Rao lower bounds on the variance of the estimates of the angles when the projection are corrupted by additive Gaussian noise. We also treat the case in which each projection is shifted by some unknown amount which must be jointly estimated with the view angles. Motivated by the stability results and relatively small values of the error bounds, we construct a simple algorithm to approximate the ML estimator and demonstrate that the problem can be feasibly solved in the presence of noise. Simulations using this simple estimator on a variety of phantoms show excellent performance at low to moderate noise levels, essentially achieving the Cramer-Rao bounds.

We present a new fast reconstruction algorithm for parallel beam tomography. The new algorithm is an accelerated version of the standard filtered backprojection (FBP) reconstruction, and uses a hierarchical decomposition of the backprojection operation to reduce the computational cost from O(N(3)) to O(N(2)log(2 )N). We discuss the choice of the various parameters that affect the behavior of the algorithm, and present numerical studies that demonstrate the cost versus distortion tradeoff. Comparisons with Fourier reconstruction algorithms and a multilevel inversion algorithm by Brandt et al., both of which also have O(N(2)log(2)N) cost, suggest that the proposed hierarchical scheme has a superior cost versus distortion performance. It offers RMS reconstruction errors comparable to the FBP with considerable speedup. For an example with a 512 x 512-pixel image and 1024 views, the speedup achieved with a particular implementation is over 40 fold, with reconstructions visually indistinguishable from the FBP.

A novel algorithm for fast computation of tomographic image projections is presented. The method comprises a decomposition of an image into subimages followed by an aggregation of projections computed for the subimages. The multilevel domain decomposition algorithm is formulated as a recursive procedure. The computational cost of the proposed algorithm is comparable to that of FFT-based techniques while it appears to be more flexible than the latter. Numerical results demonstrate the effectiveness of the method.

We present a global Ziv-Zakai (1969) type lower bound on the mean square error for estimation of signal parameter vectors, where some components of the distortion function may be periodic. Periodic distortion functions arise naturally in the context of direction of arrival or phase estimation problems. The bound is applied to an image registration problem, and compared to the performance of the maximum-likelihood estimator (MLE).

We examine the problem of periodic nonuniform sampling of a multiband signal and its reconstruction from the samples. This sampling scheme, which has been studied previously, has an interesting optimality property that uniform sampling lacks: one can sample and reconstruct the class /spl Bscr/(/spl Fscr/) of multiband signals with spectral support /spl Fscr/, at rates arbitrarily close to the Landau (1969) minimum rate equal to the Lebesgue measure of /spl Fscr/, even when /spl Fscr/ does not tile R under translation. Using the conditions for exact reconstruction, we derive an explicit reconstruction formula. We compute bounds on the peak value and the energy of the aliasing error in the event that the input signal is band-limited to the "span of /spl Fscr/" (the smallest interval containing /spl Fscr/) which is a bigger class than the valid signals /spl Bscr/(/spl Fscr/), band-limited to /spl Fscr/. We also examine the performance of the reconstruction system when the input contains additive sample noise.

We introduce confidence region techniques for analyzing and visualizing the performance of two-dimensional parametric shape estimators. Assuming an asymptotically normal and efficient estimator for a finite parameterization of the object boundary, Cramer-Rao bounds are used to define an asymptotic confidence region, centered around the true boundary. Computation of the probability that an entire boundary estimate lies within the confidence region is a challenging problem, because the estimate is a two-dimensional nonstationary random process. We derive lower bounds on this probability using level crossing statistics. The same bounds also apply to asymptotic confidence regions formed around the estimated boundaries, lower-bounding the probability that the entire true boundary lies within the confidence region. The results make it possible to generate asymptotic confidence regions for arbitrary prescribed probabilities. These asymptotic global confidence regions conveniently display the uncertainty in various geometric parameters such as shape, size, orientation, and position of the estimated object, and facilitate geometric inferences. Numerical simulations suggest that the new bounds are quite tight.

We address the problem of restoring an image from its noisy convolutions with two or more unknown finite impulse response (FIR) filters. We develop theoretical results about the existence and uniqueness of solutions, and show that under some generically true assumptions, both the filters and the image can be determined exactly in the absence of noise, and stably estimated in its presence. We present efficient algorithms to estimate the blur functions and their sizes. These algorithms are of two types, subspace-based and likelihood-based, and are extensions of techniques proposed for the solution of the multichannel blind deconvolution problem in one dimension. We present memory and computation-efficient techniques to handle the very large matrices arising in the two-dimensional (2-D) case. Once the blur functions are determined, they are used in a multichannel deconvolution step to reconstruct the unknown image. The theoretical and practical implications of edge effects, and "weakly exciting" images are examined. Finally, the algorithms are demonstrated on synthetic and real data.

We address the problem of restoring an image from its noisy convolutions with two or more blur functions (channels). Deconvolution from multiple blurs is, in general, better conditioned than from a single blur, and can be performed without regularization for moderate noise levels. We characterize the problem of missing data at the image boundaries, and show that perfect reconstruction is impossible (even in the no-noise case) almost surely unless there are at least three channels. Conversely, when there are at least three channels, we show that perfect reconstruction is not only possible almost surely in the absence of noise, but also that it can be accomplished by finite impulse response (FIR) filtering. Such FIR reconstruction is vastly more efficient computationally than the least-squares solution, and is suitable for low noise levels. Even in the high-noise case, the estimates obtained by FIR filtering provide useful starting points for iterative least-squares algorithms. We present results on the minimum possible sizes of such deconvolver filters. We derive expressions for the mean-square errors in the FIR reconstructions, and show that performance comparable to that of the least-squares reconstruction may be obtained with relatively small deconvolver filters. Finally, we demonstrate the FIR reconstruction on synthetic and real data.

Markov random field (MRF) image segmentation algorithms have been extensively studied, and have gained wide acceptance. However, almost all of the work on them has been experimental. This provides a good understanding of the performance of existing algorithms, but not a unified explanation of the significance of each component. To address this issue, we present a theoretical analysis of several MRF image segmentation criteria. Standard methods of signal detection and estimation are used in the theoretical analysis, which quantitatively predicts the performance at realistic noise levels. The analysis is decoupled into the problems of false alarm rate, parameter selection (Neyman-Pearson and receiver operating characteristics), detection threshold, expected a priori boundary roughness, and supervision. Only the performance inherent to a criterion, with perfect global optimization, is considered. The analysis indicates that boundary and region penalties are very useful, while distinct-mean penalties are of questionable merit. Region penalties are far more important for multispectral segmentation than for greyscale. This observation also holds for Gauss-Markov random fields, and for many separable within-class PDFs. To validate the analysis, we present optimization algorithms for several criteria. Theoretical and experimental results agree fairly well.

We present two "fast" approaches to the NP-hard problem of computing a maximally sparse approximate solution to linear inverse problems, also known as the best subset selection. The first approach, a heuristic, is an iterative algorithm globally convergent to sparse elements of any given convex, compact S/spl sub/R/sup mx/. We demonstrate its effectiveness in bandlimited extrapolation and in sparse filter design. The second approach is a polynomial-time greedy sequential backward elimination algorithm. We show that if A has full column rank and /spl epsiv/ is small enough, then the algorithm will find the sparsest x satisfying /spl par/Ax-b/spl par//spl les//spl epsiv/, if such exists.

We consider the problem of periodic nonuniform sampling of a multiband signal and its reconstruction from the samples. We derive the conditions for exact reconstruction and find an explicit reconstruction formula. Key features of this method are that the sampling rate can be made arbitrarily close to the minimum (Landau) rate and that it can handle classes of multiband signals that are not packable. We compute various bounds on the aliasing error due to mismodeling the spectral support and examine the performance in the presence of additive white sample noise. Finally we provide optimal designs for the reconstruction system.

The authors recently demonstrated that the view angles of tomographic projections were uniquely determined by the projection data alone for almost all objects, given enough projections. Here, they present results on the stability of the solution, as well as bounds on the variance of Convolution Back Projection (CBP) based reconstructions. To demonstrate that the problem can be feasibly solved in the presence of noise, the authors present a maximum likelihood estimator with a heuristic initialization algorithm which estimates the orientation of each projection.

We address the problem of sampling of 2D signals with sparse multi-band spectral structure. We show that the signal can be sampled at a fraction of the its Nyquist density determined by the occupancy of the signal in its frequency domain, but without explicit knowledge of its spectral structure. We nd that such a signal can almost surely be reconstructed from its multi-coset samples provided that a universal pattern is used. Also, the scheme can attain the Landau-Nyquist minimum density asymptotically. The spectrum blind feature of our reconstruction scheme has potential applications in Fourier imaging. We apply the sampling scheme on a test image to demonstrate its performance. 1.

We introduce a generalization of a deterministic relaxation algorithm for edge-preserving regularization in linear inverse problems. This algorithm transforms the original (possibly nonconvex) optimization problem into a sequence of quadratic optimization problems, and has been shown to converge under certain conditions when the original cost functional being minimized is strictly convex. We prove that our more general algorithm is globally convergent (i.e., converges to a local minimum from any initialization) under less restrictive conditions, even when the original cost functional is nonconvex. We apply this algorithm to tomographic reconstruction from limited-angle data by formulating the problem as one of regularized least-squares optimization. The results demonstrate that the constraint of piecewise smoothness, applied through the use of edge-preserving regularization, can provide excellent limited-angle tomographic reconstructions. Two edge-preserving regularizers-one convex, the other nonconvex-are used in numerous simulations to demonstrate the effectiveness of the algorithm under various limited-angle scenarios, and to explore how factors, such as the choice of error norm, angular sampling rate and amount of noise, affect the reconstruction quality and algorithm performance. These simulation results show that for this application, the nonconvex regularizer produces consistently superior results.

We address the problem of parallel beam tomographic reconstruction when the angles at which the projections are taken are unknown. The problem arises in medical imaging owing to patient motion, and in imaging of viruses from a single projection of many identical units at random orientations. We determine conditions for unique identifiability of the angles from the projection data alone, and derive bounds on the variance of estimators of those angles in the presence of noise. Finally, we present a maximum likelihood estimator, along with a heuristic initialization procedure. Numerical simulations on a test phantom show excellent agreement with the bounds, and nearly perfect reconstructions at moderate noise levels.

We address the problem of estimating the motion of a wide-band source from single passive sensor measurements, for example, estimation of the speed and position of a car moving on a road from the recording of its acoustic signature at a microphone located next to the road. We present a new computationally efficient method based on a time-varying ARMA model for Doppler-shifted random processes. Unlike previously proposed approaches which rely on a "local" periodicity hypothesis for the signal source, or a cyclostationary assumption, our method assumes only that the source is stationary and admits a rational (ARMA) model. The method is tested on synthetic and real acoustic data.

We consider the sampling of bandlimited spatiotemporal signals subject to the time-sequential (TS) constraint that only one spatial position can be sampled at any given time. Using the powerful techniques of lattice theory, we develop a new unifying theory linking TS sampling with generalized multidimensional sampling. The results have a geometric nature, involving simultaneous packing of the spectral and spatial supports in their respective domains. We provide a complete characterization of TS lattice patterns, and, extending the study to temporally nonuniform patterns, analyze their minimum and average temporal sampling rates. Unlike previous studies of TS sampling, our results apply to very general multidimensional spatial and spectral supports. We present tight bounds on the temporal parameters of those TS sampling patterns that produce zero aliasing error. The use of a TS sampler for bufferless source coding of spatiotemporal signals is considered as an attractive possibility.

For pt.I see ibid., vol.43, no.1, p.190-207 (1997). We consider the sampling of bandlimited spatiotemporal signals subject to the time-sequential (TS) constraint that only one spatial position can be sampled at any given time. Part I of this paper developed a new unifying theory linking TS sampling with generalized multidimensional sampling. It provided a complete characterization of time-sequential lattice patterns, including tight bounds on the temporal parameters of those time-sequential sampling patterns that produce zero aliasing error. In this paper we present large space-spatial-bandwidth product asymptotics for these bounds. One of the surprising results is that in many cases, there exist optimal patterns, for which, asymptotically, there is no extra penalty for lattice sampling subject to the time-sequential constraint, as compared to unconstrained multidimensional sampling. The implication to source coding is that an optimum encoder for spatiotemporal signals can be implemented with no buffering or other processing using a time-sequential sampler. The results apply to very general multidimensional spatial and spectral supports (star shaped, or at most convex).

We consider the problem of detecting and classifying an unknown number of multiple simultaneous Gaussian processes with unknown variances given a finite length observation of their sum and a dictionary of candidate models for the signals. The optimal minimum description length (MDL) detector is presented. Asymptotic and quadratic approximations of the MDL criterion are derived, and regularization algorithms for their efficient implementation are described. The performance of the algorithms is illustrated by numerical simulations. Interpretations in terms of vector quantization and in model-based spectral analysis are discussed together with applications and possible extensions.

We propose a universal sampling pattern and corresponding reconstruction algorithms that guarantee well-conditioned reconstruction of all multiband signals with a given spectral occupancy bound without prior knowledge of the spectral support. It is shown that such a universal sampling pattern can asymptotically achieve the Nyquist-Landau (1957) minimal sampling rate. Also, the new design method replaces the nonaliasing or packability criterion for a reconstructive sampling pattern with a more lenient criterion, allowing reconstruction of signals aliased by sampling.

We present an iterative algorithm for computing sparse solutions (or sparse approximate solutions) to linear inverse problems. The algorithm is intended to supplement the existing arsenal of techniques. It is shown to converge to the local minima of a function of the form used for picking out sparse solutions, and its connection with existing techniques explained. Finally, it is demonstrated on subset selection and deconvolution examples. The fact that the proposed algorithm is sometimes successful when existing greedy algorithms fail is also demonstrated.

We consider 2-D multiband signals, with a given bound on their spectral occupancy (the occupied fraction of the area of a bounding box of the spectral support). We propose a universal sampling pattern that guarantees well-conditioned reconstruction of all such signals. Such a universal sampling pattern can asymptotically achieve the Nyquist-Landau (1967) minimal sampling rate, determined by the spectral occupancy. Compared to 'Nyquist' patterns that avoid aliasing, for sparse spectral supports our design offers considerable reduction in sampling rate. Furthermore, we propose algorithms allowing reconstruction to be done blindly-without prior knowledge of the spectral support, other than its bounding box. The results apply to both continuous and discrete-time signals, and directly generalize to M-D. This work extends our analogous results for the 1D case.

We address the problem of restoring an image from its noisy convolutions with two or more unknown blur functions. We extend some of the results developed for the multichannel blind deconvolution problem in one dimension. When the unknown blur functions have no common factors, we present algorithms to estimate them quickly and accurately. Once the blur functions are available, they can be used to reconstruct the unknown image. We show that, under certain conditions, the last step can be achieved by FIR filtering with a perfect reconstruction filter bank. Some results on the effects of noise on these algorithms are also presented.

We use a series-expansion approach and an operator framework to derive a new, fast, and accurate Fourier algorithm for iterative tomographic reconstruction. This algorithm is applicable for parallel-ray projections collected at a finite number of arbitrary view angles and radially sampled at a rate high enough that aliasing errors are small. The conjugate gradient (CG) algorithm is used to minimize a regularized, spectrally weighted least-squares criterion, and we prove that the main step in each iteration is equivalent to a 2-D discrete convolution, which can be cheaply and exactly implemented via the fast Fourier transform (FFT). The proposed algorithm requires O(N(2)logN) floating-point operations per iteration to reconstruct an NxN image from P view angles, as compared to O(N (2)P) floating-point operations per iteration for iterative convolution-backprojection algorithms or general algebraic algorithms that are based on a matrix formulation of the tomography problem. Numerical examples using simulated data demonstrate the effectiveness of the algorithm for sparse- and limited-angle tomography under realistic sampling scenarios. Although the proposed algorithm cannot explicitly account for noise with nonstationary statistics, additional simulations demonstrate that for low to moderate levels of nonstationary noise, the quality of reconstruction is almost unaffected by assuming that the noise is stationary.

This paper addresses the exploratory visualization of multispectral image data. In such data, each component of the vector pixel corresponds to a different imaging modality or a different combination of imaging parameters, and may provide different levels of contrast sensitivity between different regions of the underlying image. We address the problem of presenting this multidimensional data to human observers by synthesizing a display matched to their visual capabilities. Specifically, we seek to determine a data-adaptive linear projection of the vector data to one dimension that produces a grayscale image providing maximum discrimination between the different regions of the underlying object. The approach is equivalent to the extraction of the best linear feature of the vector field. Several new feature-extraction criteria that take into account both the spatial and multivariate structures of the data are proposed and illustrated by simulations on test images.

We present a pair of sharp lower and upper bounds on the 2-norm of the aliasing error in general multiband sampling representations for not necessarily bandlimited multidimensional functions. These bounds improve and generalize previous bounds. They also complement a uniform upper bound due to Higgins (1985).

Presents an overview of two developments in tomography: design of optimum scan patterns for time-varying objects; and an efficient iterative edge-preserving algorithm for limited-angle data. The first development involves the introduction of a new problem definition and changing the "rules of the game" by unconventional acquisition formats. It also employ the mathematical tools of lattice theory, which have seen relatively little use in this area. The second development, on the other hand, addresses a classical and long standing problem, by a combination of more rigorous analysis and modeling with some heuristic twists.

We consider the problem of detecting and classifying an unknown number of multiple simultaneous Gaussian autoregressive (AR) signals with unknown variances given a finite length observation of their sum and a dictionary of candidate AR models. We show that the problem reduces to the maximum likelihood (ML) estimation of the variances of the AR components for every subset from the dictionary. The "best" subset of AR components is then found by applying the minimum description length (MDL) principle. The ML estimates of the variances are obtained by combining the EM algorithm with the Rauch-Tung-Striebel optimal smoother. The performance of the algorithm is illustrated by numerical simulations. Possible improvements of the method are discussed.

Uses a series-expansion approach and an operator framework to derive a new, fast and accurate, iterative tomographic reconstruction algorithm applicable for parallel-ray projections that have been collected at a finite number of arbitrary view angles and have been radially sampled at a rate high enough so that aliasing errors are small. The authors use the conjugate gradient algorithm to minimize a regularized least squares criterion, and prove that the main step in each iteration is equivalent to a 2-D discrete convolution, which can be cheaply and exactly implemented via the FFT. The proposed algorithm requires O(N/sup 2/ log N) multiplies per iteration to reconstruct an N/spl times/N image from P view angles, and requires the storage of half of a 2N/spl times/2N PSF.

We demonstrate that the constraint of piecewise smoothness, applied through the use of edge-preserving regularization, can provide excellent tomographic reconstructions from limited-angle data. The tomography problem is formulated as a regularized least-squares optimization problem, and is then solved using a generalization of a recently proposed deterministic relaxation algorithm. This algorithm has been shown to converge under certain conditions when the original cost functional being minimized is convex. We have proven that our more general algorithm is globally convergent under less restrictive conditions, even when the original cost functional is nonconvex. Simulation results demonstrate the effectiveness of the algorithm, and show that for moderate to high photon counts, spectrally weighted error norms perform as well as, or better than a standard error norm that is commonly used for Poisson-distributed data. This suggests that a recently proposed fast Fourier algorithm, which is restricted to using a spectrally weighted error norm, can be used in many practical limited-angle problems to perform the minimization needed by the deterministic relaxation algorithm.

Shows how the separable two-dimensional wavelet representation leads naturally to an efficient multiresolution tomographic reconstruction algorithm. This algorithm is similar to the conventional filtered backprojection algorithm, except that the filters are now angle dependent, and the backprojection gives the wavelet coefficients of the reconstruction, which are then used to synthesize the reconstruction at various resolution levels. By reconstructing only a small localized region at high resolution, the authors show how radiation exposure and computation can be significantly reduced, compared to a standard reconstruction.

The authors consider the tomographic reconstruction of objects with spatially localized temporal variation, such as a thorax cross section with a beating heart. The conventional scan format, in which projections are taken progressively around the object, requires high and sometimes infeasible scan rates to avoid motion artifacts in the reconstructed images. The authors formulate the problem of data acquisition as a time-sequential sampling problem of spatially and temporally bandlimited signals, where only one view can be taken at a time, but the time interval between successive views is independent of their angular separation. These conditions, naturally satisfied in magnetic resonance imaging and in X-ray CT using the Imatron system, can also be satisfied by a conventional system with a continuously and rapidly spinning gantry with source pulsing. Theoretical analysis, which includes tight performance bounds, shows that by using an optimally scrambled angular sampling order, the required scan rate can be lowered as much as four times, while preserving image quality. The analysis also greatly simplifies the design of the optimum scan pattern by reducing it to a constrained geometric packing problem.

For pt.I see ibid., vol.4, no.5, p.642-53 (1995). In pt.I the authors presented a theoretical analysis of tomographic reconstruction of objects with spatially localized temporal variation, such as a thorax cross section with a beating heart. That analysis showed that by using an optimally scrambled angular sampling order, the scan rate required to avoid motion artifacts in the reconstructed images can be lowered as much as four times while preserving image quality. Here, the authors present a simple design procedure for the optimum choice of angular sampling pattern, which depends only on pre-specified geometric and spectral parameters and the desired spatial resolution. The resulting patterns have a simple congruential structure. Reconstruction is accomplished by interpolation to standard time-invariant scan format, followed by conventional reconstruction. The interpolation only requires linear shift-invariant separable filtering, at a negligible computational cost. Simulation results demonstrate the technique and validate the analysis for both bandlimited and approximately bandlimited objects.

We show how the separable two-dimensional wavelet representation leads naturally to an efficient multiresolution tomographic reconstruction algorithm. This algorithm is similar to the conventional filtered backprojection algorithm, except that the filters are now angle dependent, and the backprojection gives us the wavelet coefficients of the reconstruction, which are then used to synthesize the reconstruction at various resolution levels. By reconstructing only a small localized region at high resolution, radiation exposure and computation can be significantly reduced, compared to a standard reconstruction.>

This paper addresses the problem of the visualization of vector-valued images. Attempting to synthesize a display matched to the capabilities of a human observer, we have reduced the problem to the extraction of the best linear feature of the vector field. In previous work, we have proposed and demonstrated several new nonparametric feature extraction criteria (projection indices) that make use of both the spatial and multivariate structures of the data. We present a theoretical analysis of these projection indices and a Monte-Carlo study of their effectiveness. The study uses performance measures derived from a decision-theoretic model of the human observer.>

Several multiscale objective functions for the direct segmentation of tomographic images are presented. Standard methods of signal detection and estimation are used to develop a theoretical performance analysis, which quantitatively predicts the performance at realistic noise levels. The analysis compares the relative merit of multiscale and monoscale segmentation, and shows the impact of the Shepp-Logan skull's quantization error.>

Summary form only given. We consider the sampling of band-limited spatio-temporal signals subject to the time-sequential constraint that only one spatial sample can be taken at a given time. The question of interest is to design an efficient sampling strategy that will minimise the required sampling rate. Signals with a finite spatial support are considered.

This paper addresses the problem of the visualization of vector-valued images. It is attempted to synthesize a display matched to the capabilities of a human observer. The problem is reduced to the extraction of the best linear feature of the vector field. Several new nonparametric feature extraction criteria (projection indices) that make use of both the spatial and multivariate structures of the data have been recently proposed and demonstrated. A theoretical analysis of these projection indices and a Monte-Carlo study of their effectiveness is presented here. The study uses performance measures derived from a decision-theoretic model of the human observer.

Sampling of signals that vary in time and have one or more spatial dimensions is studied for constrained sampling sets. The constraint imposed is that only one spatial sample can be taken at a given time, hence the name time-sequential sampling. J. Allebach (1984) has shown previously that the amount of aliasing error is not only a function of the sampling rates, but is also strongly dependent on the order in which spatial sample points are taken. A new design technique for finding optimal sampling patterns that minimize the sampling rates and produce zero aliasing error is developed by viewing time-sequential sampling as a specialized case of generalized two-dimensional sampling. New lower bounds for sampling rates required to produce zero aliasing error are given. These bounds are then used as stopping criteria for the aforementioned design technique. Theorems are given which state conditions under which the design problem reduces to a general two-dimensional sampling problem.>

The restoration of an image modeled by piecewise-constant polygonal patches from its blurred (bandlimited) and noise corrupted version is considered. Under this model, the line-integral projections of the data image are piecewise linear signals, blurred and corrupted by noise. The break points and the associated amplitude parameters of each projection are estimated by minimizing the 1-D stochastic complexity of the projection using a recently proposed dynamic programming technique. The final image is reconstructed by convolution backprojection.>

Minimax-optimal interpolation algorithms minimize the error resulting from the worst signal from an allowable class. The result is presented that if this class lies in a Hilbert space, the minimax-optimal algorithm is independent of or invariant to the error norm. The result encompasses a broad class of inverse problems.>

The fundamental limits on the maximum number D/sub max/ of cochannel wideband emitters uniquely resolvable by a passive K-element sensor array are studied. It is shown that for uncorrelated emitters D/sub max/ is only O(K square root L), where L is the measurement time-bandwidth product. These results extend the author's recent result, that for a uniform linear array with uncorrelated cochannel wideband emitters D/sub max/ approximately=K L/2. Hence, D/sub max/ of a given array for cochannel wideband signals is essentially limited only by the observation interval, rather than by the number of sensors.>

The problem of fitting a model composed of a number of superimposed signals to noisy data using the maximum likelihood (ML) criterion is considered. A dynamic programming (DP) algorithm which solves the problem efficiently is presented. An asymptotic property of the estimates is derived, and a bound on the bias of the estimates is given. The bound is then computed using perturbation analysis and compared with computer simulation results. The results show that the DP algorithm is a versatile and efficient algorithm for parameter estimation. In practical applications, the estimates can be refined by a local search (e.g., the Gauss-Newton method) of the exact ML criterion, initialized by the DP estimates.>

A model-based approach for superresolution signal reconstruction from noisy bandlimited Fourier data is proposed. The approach combines the virtues of parametric and nonparametric techniques by maximum-likelihood fitting of the data by a mixture of exponentials and smooth basis functions. Performance bounds are derived and analyzed, and a model computationally efficient algorithm is described. The performance of the algorithm in simulations closely matches the bounds over a wide range of operating conditions. Overall, the reconstructions are far superior to those obtained by traditional Fourier transform processing.>

The problem of fitting a model composed of a number of superimposed signals to noisy data using the maximum-likelihood criterion is considered. A local interaction model is established through the study of Cramer-Rao bound. For such models, the global extremum of the criterion is found efficiently by dynamic programming. An approximate version of the algorithm is developed to further reduce the computation. Using the minimum description length principle, it is shown that the dynamic programming method can be easily adapted to determine the number of signals as well.>

An algorithm for detecting and estimating the parameters of an unknown number of closely spaced, superimposed noisy echoes of a signal of unknown and arbitrary shape is derived. The algorithm exploits an approximate invariance structure in the frequency domain that allows the ESPRIT algorithm to be used for parameter estimation. An extension of the algorithm is applicable to the resolution of superimposed pulses of unknown and possibly different shapes. Computer simulation results for the algorithm are compared with the corresponding Cramer-Rao performance bounds.>

A data acquisition scheme combining the axial translation of the object with rotation of the imaging gantry is introduced for three-dimensional computerized tomography (CT), and a reconstruction algorithm for its implementation is explored. A computationally attractive interpolation scheme that converts the data to standard CT format and permits reconstruction by existing algorithms is proposed. The approach is to convert by interpolation the helical-scan projection data into standard planar scan format and then use a standard 2-D reconstruction technique, such as convolution backprojection, on each slice. Optimum interpolation coefficients are derived, minimizing a worst case normalized maximum error magnitude criterion. The theoretical predictions are illustrated by simulation results.>

An estimation approach is described for three-dimensional reconstruction from line integral projections using incomplete and very noisy data. Generalized cylinders parameterized by stochastic dynamic models are used to represent prior knowledge about the properties of objects of interest in the probed domain. The object models, a statistical measurement model, and the maximum a posteriori probability performance criterion are combined to reformulate the reconstruction problem as a computationally challenging nonlinear estimation problem. For computational feasibility, a suboptimal hierarchical algorithm is described whose individual steps are locally optimal and are combined to satisfy a global optimality criterion. The formulation and algorithm are restricted to objects whose center axis is a single-valued function of a fixed spatial coordinate. Simulation examples demonstrate accurate reconstructions with as few as four views in a 135 degrees sector, at an average signal-to-noise ratio of 3.3.>

A new approach to optimum beamforming in the presence of signal correlated interfences that completely eliminates the signal cancellation problem is described. Three new, fundamentally distinct beamformers corresponding to different optimality criteria are derived by exploiting the underlying signal model.

A unified framework for the exact Maximum Likelihood estimation of the parameters of superimposed exponential signals in noise, encompassing both the single and the multiexperiment cases (respectively the time series and the array problems), is presented. An exact expression for the ML criterion is derived in terms of the prediction polynomial of the noiseless signal, and an iterative algorithm for the maximization of this criterion is presented. A simulation example shows the estimator to be capable of providing more accurate frequency estimates than currently existing techniques.

An estimation approach to three dimensional reconstruction from projections, with incomplete and very noisy data, is suggested. Using a stochastic dynamic model for the object of interest in the probed domain, the reconstruction problem is reformulated as a nonlinear state estimation problem of small dimensionality, and an approximate MMSE globally optimal algorithm for its solution is presented. The algorithm, which is recursive in a hybrid frequency-space domain, operates directly on the Fourier transformed projection data, eliminating altogether the attempt to invert the projection integral equation. The computational requirements compare favorably with those of conventional reconstruction procedures, which fail in the limited and noisy data case.