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

Scholarly Works (9 results)

  • Article
  • Peer Reviewed
Graduate (2009)
Compressed sensing has a wide range of applications that include error correction, imaging, radar and many more. Given a sparse signal in a high dimensional space, one wishes to reconstruct that signal accurately and efficiently from a number of linear measurements much less than its actual dimension. Although in theory it is clear that this is possible, the difficulty lies in the construction of algorithms that perform the recovery efficiently, as well as determining which kind of linear measurements allow for the reconstruction. There have been two distinct major approaches to sparse recovery that each present different benefits and shortcomings. The first, L1-minimization methods such as Basis Pursuit, use a linear optimization problem to recover the signal. This method provides strong guarantees and stability, but relies on Linear Programming, whose methods do not yet have strong polynomially bounded runtimes. The second approach uses greedy methods that compute the support of the signal iteratively. These methods are usually much faster than Basis Pursuit, but until recently had not been able to provide the same guarantees. This gap between the two approaches was bridged when we developed and analyzed the greedy algorithm Regularized Orthogonal Matching Pursuit (ROMP). ROMP provides similar guarantees to Basis Pursuit as well as the speed of a greedy algorithm. Our more recent algorithm Compressive Sampling Matching Pursuit (CoSaMP) improves upon these guarantees, and is optimal in every important aspect.
    • Article
    • Peer Reviewed
    Graduate (2009)
    Compressed sensing has shown that it is possible to reconstruct sparse high dimensional signals from few linear measurements. In many cases, the solution can be obtained by solving an L1-minimization problem, and this method is accurate even in the presence of noise. Recent a modified version of this method, reweighted L1-minimization, has been suggested. Although no provable results have yet been attained, empirical studies have suggested the reweighted version outperforms the standard method. Here we analyze the reweighted L1-minimization method in the noisy case, and provide provable results showing an improvement in the error bound over the standard bounds.
      • Article
      • Peer Reviewed
      Graduate (2009)
      The Kaczmarz method is an iterative algorithm for solving systems of linear equations Ax=b. Theoretical convergence rates for this algorithm were largely unknown until recently when work was done on a randomized version of the algorithm. It was proved that for overdetermined systems, the randomized Kaczmarz method converges with expected exponential rate, independent of the number of equations in the system. Here we analyze the case where the system Ax=b is corrupted by noise, so we consider the system where Ax is approximately b + r where r is an arbitrary error vector. We prove that in this noisy version, the randomized method reaches an error threshold dependent on the matrix A with the same rate as in the error-free case. We provide examples showing our results are sharp in the general context.
        • Article
        • Peer Reviewed
        Faculty (2007)
        This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements -- L_1-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of the Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of the L_1-minimization. Our algorithm ROMP reconstructs a sparse signal in a number of iterations linear in the sparsity (in practice even logarithmic), and the reconstruction is exact provided the linear measurements satisfy the Uniform Uncertainty Principle.
          • Article
          • Peer Reviewed
          Faculty (2007)
          We demonstrate a simple greedy algorithm that can reliably recover a d-dimensional vector v from incomplete and inaccurate measurements x. Here our measurement matrix is an N by d matrix with N much smaller than d. Our algorithm, Regularized Orthogonal Matching Pursuit (ROMP), seeks to close the gap between two major approaches to sparse recovery. It combines the speed and ease of implementation of the greedy methods with the strong guarantees of the convex programming methods. For any measurement matrix that satisfies a Uniform Uncertainty Principle, ROMP recovers a signal with O(n) nonzeros from its inaccurate measurements x in at most n iterations, where each iteration amounts to solving a Least Squares Problem. The noise level of the recovery is proportional to the norm of the error, up to a log factor. In particular, if the error vanishes the reconstruction is exact. This stability result extends naturally to the very accurate recovery of approximately sparse signals.
            • Thesis
            • Peer Reviewed
            UCLA Electronic Theses and Dissertations (2021)

            Methods that analyze large-scale data and make predictions based on data are increasingly prevalent in a variety of industries. These methods are often complex, rely on a variety of subroutines and are applied in settings for which they lack theoretical guarantees. Additionally, storage requirements and computational speed are crucial to the feasibility of methods at large-scales.Here, we derive theoretical guarantees for machine learning and data analytic subroutines such as matrix completion and optimization. We also extend the development of classification methods for binary, compressed data. More specifically, we consider the following. We analyze a regularized variant of the standard nuclear-norm minimization problem for low-rank matrix completion for settings in which smaller entries are more likely to be missing. We derive convergence guarantees for a gradient descent method for solving support vector machines and compare the derived convergence guarantees to those of existing strategies. We analyze adaptive sampling strategies for sketch-and-project methods for solving large-scale least- squares problems. We develop hierarchical and iterative extensions to the simple classification method for binary data introduced in [NSW17].

              Cover page: Analytic methods for large-scale data
              • Thesis
              • Peer Reviewed
              UCLA Electronic Theses and Dissertations (2023)

              In this thesis, we present a myriad of applications of online matrix and tensor dictionarylearning algorithms to the analysis of time series and image data, as well as a theoretical analysis of our algorithm, Online CP-Dictionary Learning (OCPDL). First, we present a method which applies online nonnegative matrix factorization (ONMF), an algorithm which learns a sparse, nonnegative representation of streaming data, to perform joint dictionary learning on multivariate COVID-19 time-series data, followed by a certain “restrict and predict" algorithm to tackle the future time regression problem. Next, we apply ONMF to meteorological time series data, as well as to video data, and demonstrate the particular utility of online as opposed to online algorithms in dealing with said data. In the following section, we present our extension of ONMF, our OCPDL algorithm, as well as a proof of some convergence guarantees.

                Cover page: Online Nonnegative CP-Dictionary Learning with Applications to Multimodal Data
                • Article
                • Peer Reviewed
                Faculty (2016)
                We combine two iterative algorithms for solving large-scale systems of linear inequalities, the relaxation method of Agmon, Motzkin et al. and the randomized Kaczmarz method. In doing so, we obtain a family of algorithms that generalize and extend both techniques. We prove several convergence results, and our computational experiments show our algorithms often outperform the original methods.
                  • Article
                  • Peer Reviewed
                  UC Davis Previously Published Works (2021)
                  Machine learning algorithms typically rely on optimization subroutines and are well known to provide very effective outcomes for many types of problems. Here, we flip the reliance and ask the reverse question: can machine learning algorithms lead to more effective outcomes for optimization problems? Our goal is to train machine learning methods to automatically improve the performance of optimization and signal processing algorithms. As a proof of concept, we use our approach to improve two popular data processing subroutines in data science: stochastic gradient descent and greedy methods in compressed sensing. We provide experimental results that demonstrate the answer is “yes”, machine learning algorithms do lead to more effective outcomes for optimization problems, and show the future potential for this research direction. In addition to our experimental work, we prove relevant Probably Approximately Correct (PAC) learning theorems for our problems of interest. More precisely, we show that there exists a learning algorithm that, with high probability, will select the algorithm that optimizes the average performance on an input set of problem instances with a given distribution.
                    Top