Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (35 results)

  • Article
  • Peer Reviewed
Faculty (2000)
We consider three problems for Gabor frames that have recently received much attention. The first problem concerns the approximation of dual Gabor frames in $L_2(R)$ by finite-dimensional methods. Utilizing Wexler-Raz type duality relations we derive a method to approximate the dual Gabor frame, that is much simpler than previously proposed techniques. Furthermore it enables us to give estimates for the approximation rate when the dimension of the finite model approaches infinity. The second problem concerns the relation between the decay of the window function $g$ and its dual $\gamma$. Based on results on commutative Banach algebras and Laurent operators we derive a general condition under which the dual $\gamma$ inherits the decay properties of $g$. The third problem concerns the design of pulse shapes for orthogonal frequency division multiplex (OFDM) systems for time- and frequency dispersive channels. In particular, we provide a theoretical foundation for a recently proposed algorithm to construct orthogonal transmission functions that are well localized in the time-frequency plane.
    • Article
    • Peer Reviewed
    Faculty (1999)
    A shift-invariant system is a collection of functions $\{g_{m,n}\}$ of the form $g_{m,n}(k) = g_m(k-an)$. Such systems play an important role in time-frequency analysis and digital signal processing. A principal problem is to find a dual system $\gamma_{m,n}(k) = \gamma_m(k-an)$ such that each function $f$ can be written as $f = \sum < f, \gamma_{m,n} > g_{m,n}$. The mathematical theory usually addresses this problem in infinite dimensions (typically in $L_2(R)$ or $l_2(Z)$), whereas numerical methods have to operate with a finite-dimensional model. Exploiting the link between the frame operator and Laurent operators with matrix-valued symbol, we apply the finite section method to show that the dual functions obtained by solving a finite-dimensional problem converge to the dual functions of the original infinite-dimensional problem in $l_2(Z)$. For compactly supported $g_{m,n}$ (FIR filter banks) we prove an exponential rate of convergence and derive explicit expressions for the involved constants. Further we investigate under which conditions one can replace the discrete model of the finite section method by the periodic discrete model, which is used in many numerical procedures. Again we provide explicit estimates for the speed of convergence. Some remarks on tight frames complete the paper.
      • Article
      • Peer Reviewed
      Faculty (1999)
      Trigonometric polynomials are widely used for the approximation of a smooth function $f$ from a set of nonuniformly spaced samples $\{f(x_j)\}_{j=0}^{N-1}$. If the samples are perturbed by noise, controlling the smoothness of the trigonometric approximation becomes an essential issue to avoid overfitting and underfitting of the data. Using the polynomial degree as regularization parameter we derive a multi-level algorithm that iteratively adapts to the least squares solution of optimal smoothness. The proposed algorithm computes the solution in at most $\cal{O}(NM + M^2)$ operations ($M$ being the polynomial degree of the approximation) by solving a family of nested Toeplitz systems. It is shown how the presented method can be extended to multivariate trigonometric approximation. We demonstrate the performance of the algorithm by applying it in echocardiography to the recovery of the boundary of the Left Ventricle.
        • Article
        • Peer Reviewed
        Faculty (2000)
        We give an overview of recent developments in the problem of reconstructing a band-limited signal from non-uniform sampling from a numerical analysis view point. It is shown that the appropriate design of the finite-dimensional model plays a key role in the numerical solution of the non-uniform sampling problem. In the one approach (often proposed in the literature) the finite-dimensional model leads to an ill-posed problem even in very simple situations. The other approach that we consider leads to a well-posed problem that preserves important structural properties of the original infinite-dimensional problem and gives rise to efficient numerical algorithms. Furthermore a fast multilevel algorithm is presented that can reconstruct signals of unknown bandwidth from noisy non-uniformly spaced samples. We also discuss the design of efficient regularization methods for ill-conditioned reconstruction problems. Numerical examples from spectroscopy and exploration geophysics demonstrate the performance of the proposed methods.
          • Article
          • Peer Reviewed
          Faculty (2012)
          Is compressive sensing overrated? Or can it live up to our expectations? What will come after compressive sensing and sparsity? And what has Galileo Galilei got to do with it? Compressive sensing has taken the signal processing community by storm. A large corpus of research devoted to the theory and numerics of compressive sensing has been published in the last few years. Moreover, compressive sensing has inspired and initiated intriguing new research directions, such as matrix completion. Potential new applications emerge at a dazzling rate. Yet some important theoretical questions remain open, and seemingly obvious applications keep escaping the grip of compressive sensing. In this paper I discuss some of the recent progress in compressive sensing and point out key challenges and opportunities as the area of compressive sensing and sparse representations keeps evolving. I also attempt to assess the long-term impact of compressive sensing.
            • Article
            • Peer Reviewed
            Faculty (2000)
            The stories told in this paper are dealing with the solution of finite, infinite, and biinfinite Toeplitz-type systems. A crucial role plays the off-diagonal decay behavior of Toeplitz matrices and their inverses. Classical results of Gelfand et al. on commutative Banach algebras yield a general characterization of this decay behavior. We then derive estimates for the approximate solution of (bi)infinite Toeplitz systems by the finite section method, showing that the approximation rate depends only on the decay of the entries of the Toeplitz matrix and its condition number. Furthermore, we give error estimates for the solution of doubly infinite convolution systems by finite circulant systems. Finally, some quantitative results on the construction of preconditioners via circulant embedding are derived, which allow to provide a theoretical explanation for numerical observations made by some researchers in connection with deconvolution problems.
              • Article
              • Peer Reviewed
              Faculty (2015)
              The design of high-precision sensing devises becomes ever more difficult and expensive. At the same time, the need for precise calibration of these devices (ranging from tiny sensors to space telescopes) manifests itself as a major roadblock in many scientific and technological endeavors. To achieve optimal performance of advanced high-performance sensors one must carefully calibrate them, which is often difficult or even impossible to do in practice. In this work we bring together three seemingly unrelated concepts, namely Self-Calibration, Compressive Sensing, and Biconvex Optimization. The idea behind self-calibration is to equip a hardware device with a smart algorithm that can compensate automatically for the lack of calibration. We show how several self-calibration problems can be treated efficiently within the framework of biconvex compressive sensing via a new method called SparseLift. More specifically, we consider a linear system of equations y = DAx, where both x and the diagonal matrix D (which models the calibration error) are unknown. By "lifting" this biconvex inverse problem we arrive at a convex optimization problem. By exploiting sparsity in the signal model, we derive explicit theoretical guarantees under which both x and D can be recovered exactly, robustly, and numerically efficiently via linear programming. Applications in array calibration and wireless communications are discussed and numerical simulations are presented, confirming and complementing our theoretical analysis.
                • Article
                • Peer Reviewed
                Faculty (2007)
                The Kaczmarz method for solving linear systems of equations is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing. Despite the popularity of this method, useful theoretical estimates for its rate of convergence are still scarce. We introduce a randomized version of the Kaczmarz method for consistent, overdetermined linear systems and we prove that it converges with expected exponential rate. Furthermore, this is the first solver whose rate does not depend on the number of equations in the system. The solver does not even need to know the whole system, but only a small random part of it. It thus outperforms all previously known methods on general extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations as well as theoretical analysis reveal that our algorithm can converge faster than the celebrated conjugate gradient algorithm. Furthermore, our theory and numerical simulations confirm a prediction of Feichtinger et al. in the context of reconstructing bandlimited functions from nonuniform sampling.
                  • Article
                  • Peer Reviewed
                  Faculty (2015)
                  The almost Mathieu operator is the discrete Schr\"odinger operator $H_{\alpha,\beta,\theta}$ on $\ell^2(\mathbb{Z})$ defined via $(H_{\alpha,\beta,\theta}f)(k) = f(k + 1) + f(k - 1) + \beta \cos(2\pi \alpha k + \theta) f(k)$. We derive explicit estimates for the eigenvalues at the edge of the spectrum of the finite-dimensional almost Mathieu operator. We furthermore show that the (properly rescaled) $m$-th Hermite function $\phi_m$ is an approximate eigenvector of this operator, and that it satisfies the same properties that characterize the true eigenvector associated to the $m$-th largest eigenvalue. Moreover, a properly translated and modulated version of $\phi_m$ is also an approximate eigenvector of this operator, and it satisfies the properties that characterize the true eigenvector associated to the $m$-th largest (in modulus) negative eigenvalue. The results hold at the edge of the spectrum, for any choice of $\theta$ and under very mild conditions on $\alpha$ and $\beta$. We also give precise estimates for the size of the "edge", and extend some of our results to the infinite dimensional case. The ingredients for our proofs comprise Taylor expansions, basic time-frequency analysis, Sturm sequences, and perturbation theory for eigenvalues and eigenvectors. Numerical simulations demonstrate the tight fit of the theoretical estimates.
                    • Thesis
                    • Peer Reviewed
                    UC Davis Electronic Theses and Dissertations (2024)

                    Inverse problems arise in many fields of engineering and science. In this dissertation, we explore various aspects of model uncertainties encountered in computational imaging applications. We will discuss some of the developments in combining convex/nonconvex optimization methods, com- pressive sensing theory, dictionary learning and data-driven hybrid methods, with domain-specific knowledge contained in physical-analytical models, in a coherent way, in solving some of the chal- lenging ill-posed inverse problems.In Chapter 1, we provide a brief introduction to inverse problems, sparsity, and compressive sensing. We introduce how imperfect sensing, dictionary learning, and prior knowledge of the signal can be incorporated into the modeling to address ill-posedness problems, paving the way for subsequent discussions on specific challenges encountered in di↵erent imaging applications. In Chapter 2, we study a form of model uncertainty that arises from uncalibrated sensing coils. We study an auto-calibration problem in which a transform-sparse signal is compressive-sensed by multiple sensors in parallel with unknown sensing parameters. The problem has an important application in parallel Magnetic Resonance Imaging (pMRI) reconstruction, where explicit coil cal- ibrations are often dicult and costly to achieve in practice. We show how ideas from convex optimization, compressive sensing and probabilistic theory can be combined together to solve the auto-calibration problem. Robust and stable recovery guarantees are derived in the presence of noise and sparsity deficiencies in the signals. For the pMRI application, our method provides a theoretically guaranteed approach to self-calibrated parallel imaging to accelerate MRI acquisitions under appropriate assumptions. We also discuss potential deep learning approaches that can serve as a future direction. The main materials presented in this chapter are based on [1] submitted to Inverse Problems. In Chapter 3, we move on to a distinct challenge that arises in Fluorescence Lifetime Imaging (FLIM). FLIM measures a convolution y = i * h + eps, where h represents the signal of inter- est. Conventional methods often involve constraining h to a low dimensional subspace B(h) (i.e. h = B(h)z). Due to the implicit dependence of B on the underlying signal, choosing a proper for- ward matrix that fits well to signals with various decaying physics is nontrivial. We propose learning the best sparse representation from fluorescence impulse response function (fIRFs) through joint deconvolution and sparse non-negative matrix factorization, and comparing the performance with traditional fitting methods that use a fixed basis. As a second step, we explore the application of utilizing the reconstructed h in cancer classification from biological tissue samples. In Chapter 4, we introduce some of the model uncertainty problems in Ptychography that are accounted for by poor calibration using multiplexing illumination. The material presented in this chapter revolves around computational considerations and the design of ecient and distributional algorithms for practical uses. We empirically demonstrate an acceleration in convergence rate if the uncertainties are solved by a separate optimization problem within common phase retrieval algorithms. And it is the first to apply such scheme to large scale problems due to our utilization of ecient coding practices and parallel computing techniques. Moreover, we propose and develop a patch-based scheme to further enhance computation.

                      Top