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

Scholarly Works (17 results)

  • Article
  • Peer Reviewed
UC Davis Previously Published Works (2018)
When attempting to develop wavelet transforms for graphs and networks, some researchers have used graph Laplacian eigenvalues and eigenvectors in place of the frequencies and complex exponentials in the Fourier theory for regular lattices in the Euclidean domains. This viewpoint, however, has a fundamental flaw: on a general graph, the Laplacian eigenvalues cannot be interpreted as the frequencies of the corresponding eigenvectors. In this paper, we discuss this important problem further and propose a new method to organize those eigenvectors by defining and measuring 'natural' distances between eigenvectors using the Ramified Optimal Transport Theory followedby embedding them into a low-dimensional Euclidean domain. We demonstrate its effectiveness using a synthetic graph as well as a dendritic tree of a retinal ganglioncell of a mouse.
    Cover page: How Can We Naturally Order and Organize Graph Laplacian Eigenvectors?Creative Commons 'BY-NC-ND' version 4.0 license
    • Article
    • Peer Reviewed
    Faculty (2001)
    A basis under which a given set of realizations of a stochastic process can be represented most sparsely (the so-called best sparsifying basis (BSB)) and the one under which such a set becomes as less statistically dependent as possible (the so-called least statistically-dependent basis (LSDB)) are important for data compression and have generated interests among computational neuroscientists as well as applied mathematicians. Here we consider these bases for a particularly simple stochastic process called ``generalized spike process'', which puts a single spike--whose amplitude is sampled from the standard normal distribution--at a random location in the zero vector of length $\ndim$ for each realization. Unlike the ``simple spike process'' which we dealt with in our previous paper and whose amplitude is constant, we need to consider the kurtosis-maximizing basis (KMB) instead of the LSDB due to the difficulty of evaluating differential entropy and mutual information of the generalized spike process. By computing the marginal densities and moments, we prove that: 1) the BSB and the KMB selects the standard basis if we restrict our basis search within all possible orthonormal bases in ${\mathbb R}^n$; 2) if we extend our basis search to all possible volume-preserving invertible linear transformations, then the BSB exists and is again the standard basis whereas the KMB does not exist. Thus, the KMB is rather sensitive to the orthonormality of the transformations under consideration whereas the BSB is insensitive to that. Our results once again support the preference of the BSB over the LSDB/KMB for data compression applications as our previous work did.
      • Article
      • Peer Reviewed
      UC Davis Previously Published Works (2010)
      In 2006, Saito and Remy proposed a new transform called the Laplace Local Sine Transform (LLST) in image processing as follows. Let f be a twice continuously differentiable function on a domain Ω. First we approximate f by a harmonic function u such that the residual component v=f−u vanishes on the boundary of Ω. Next, we do the odd extension for v, and then do the periodic extension, i.e. we obtain a periodic odd function v *. Finally, we expand v * into Fourier sine series. In this paper, we propose to expand v * into a periodic wavelet series with respect to biorthonormal periodic wavelet bases with the symmetric filter banks. We call this the Harmonic Wavelet Transform (HWT). HWT has an advantage over both the LLST and the conventional wavelet transforms. On the one hand, it removes the boundary mismatches as LLST does. On the other hand, the HWT coefficients reflect the local smoothness of f in the interior of Ω. So the HWT algorithm approximates data more efficiently than LLST, periodic wavelet transform, folded wavelet transform, and wavelets on interval. We demonstrate the superiority of HWT over the other transforms using several standard images.
        Cover page: Harmonic Wavelet Transform and Image Approximation
        • Article
        • Peer Reviewed
        UC Davis Previously Published Works (2014)
          Cover page: Hierarchical graph Laplacian eigen transforms
          • Article
          • Peer Reviewed
          Faculty (2010)
          In this article we prove the existence, uniqueness, and simplicity of a negative eigenvalue for a class of integral operators whose kernel is of the form $|x-y|^\rho$, $0 < \rho \leq 1$, $x, y \in [-a, a]$. We also provide two different ways of producing recursive formulas for the Rayleigh functions (i.e., recursion formulas for power sums) of the eigenvalues of this integral operator when $\rho=1$, providing means of approximating this negative eigenvalue. These methods offer recursive procedures for dealing with the eigenvalues of a one-dimensional Laplacian with non-local boundary conditions which commutes with an integral operator having a harmonic kernel. The problem emerged in recent work by one of the authors [45]. We also discuss extensions in higher dimensions and links with distance matrices.
            • Article
            • Peer Reviewed
            UC Davis Previously Published Works (2014)
            We propose an efficient nonlinear approximation scheme using the Polyharmonic Local Sine Transform (PHLST) of Saito and Remy combined with an algorithm to tile a given image automatically and adaptively according to its local smoothness and singularities. To measure such local smoothness, we introduce the so-called local Besov indices of an image, which is based on the pointwise modulus of smoothness of the image. Such an adaptive tiling of an image is important for image approximation using PHLST because PHLST stores the corner and boundary information of each tile and consequently it is wasteful to divide a smooth region of a given image into a set of smaller tiles. We demonstrate the superiority of the proposed algorithm using Antarctic remote sensing images over the PHLST using the uniform tiling. Analysis of such images including their efficient approximation and compression has gained its importance due to the global climate change. © 2014 American Institute of Mathematical Sciences.
              Cover page: PHLST with adaptive tiling and its application to antarctic remote sensing image approximation
              • Thesis
              • Peer Reviewed
              UC Davis Electronic Theses and Dissertations (2023)

              As network analysis tools have become more powerful over the last decade, the need has arisen for new multiscale signal processing tools, both for robust understanding of the intrinsic geometry underlying data, and for higher-order signals, incorporating not only data which lives on the vertices of a graph, but perhaps on its edges, or the faces of a triangular mesh of a manifold. In this disserta- tion, first we develop a discrete integral operator suitable for spectral embedding and partitioning of graphs, by carefully studying the development of graph Laplacian techniques from their continuous analogues on domains, and applying those developments to integral operators which commute with the continuous Laplacian. We demonstrate the operator’s effectiveness at distinguishing underly- ing geometry in scattered data, and efficient sparse techniques for performing partitioning using it. Next, we present extensions of two powerful multiscale graph signal transforms for analyzing signals defined on the κ-dimensional simplices of a simplicial complex. The previous Hierarchical Graph Laplacian Eigen Transform (HGLET) generalizes the block DCT to the graph setting, and our Hierarchical κ-Laplacian Eigen Transform (κ-HGLET) generalizes further to the simplicial complex setting. Likewise, for the previous Generalized Haar-Walsh Transform (GHWT) which generalizes the Haar-Walsh wavelet packet transform, we propose the κ-Generalized Haar-Walsh Transform (κ-GHWT). The key idea is to use the Hodge Laplacians and their variants for hierarchical bipar- titioning of the κ-dimensional simplices in a given simplicial complex, and then building localized basis functions on these partitioned subsets. We demonstrate the usefulness of the κ-HGLET and κ-GHWT on both illustrative synthetic examples and real-world simplicial complexes generated from a co-authorship/citation dataset.

                Cover page: Discrete Integral Operators on Graphs and Multiscale Transforms on Simplicial Complexes
                • Article
                • Peer Reviewed
                UC Davis Previously Published Works (2022)
                Extending computational harmonic analysis tools from the classical setting of regular lattices to the more general setting of graphs and networks is very important, and much research has been done recently. The generalized Haar–Walsh transform (GHWT) developed by Irion and Saito (2014) is a multiscale transform for signals on graphs, which is a generalization of the classical Haar and Walsh–Hadamard transforms. We propose the extended generalized Haar–Walsh transform (eGHWT), which is a generalization of the adapted time–frequency tilings of Thiele and Villemoes (1996). The eGHWT examines not only the efficiency of graph-domain partitions but also that of “sequency-domain” partitions simultaneously. Consequently, the eGHWT and its associated best-basis selection algorithm for graph signals significantly improve the performance of the previous GHWT with the similar computational cost, O(Nlog N) , where N is the number of nodes of an input graph. While the GHWT best-basis algorithm seeks the most suitable orthonormal basis for a given task among more than (1.5) N possible orthonormal bases in RN, the eGHWT best-basis algorithm can find a better one by searching through more than 0.618 · (1.84) N possible orthonormal bases in RN. This article describes the details of the eGHWT best-basis algorithm and demonstrates its superiority using several examples including genuine graph signals as well as conventional digital images viewed as graph signals. Furthermore, we also show how the eGHWT can be extended to 2D signals and matrix-form data by viewing them as a tensor product of graphs generated from their columns and rows and demonstrate its effectiveness on applications such as image approximation.
                  • Article
                  • Peer Reviewed
                  Faculty (2001)
                  Finding a basis/coordinate system that can efficiently represent an input data stream by viewing them as realizations of a stochastic process is of tremendous importance in many fields including data compression and computational neuroscience. Two popular measures of such efficiency of a basis are sparsity (measured by the expected $\ell^p$ norm, $0 < p \leq 1$) and statistical independence (measured by the mutual information). Gaining deeper understanding of their intricate relationship, however, remains elusive. Therefore, we chose to study a simple synthetic stochastic process called the spike process, which puts a unit impulse at a random location in an $n$-dimensional vector for each realization. For this process, we obtained the following results: 1) The standard basis is the best both in terms of sparsity and statistical independence if $n \geq 5$ and the search of basis is restricted within all possible orthonormal bases in $R^n$; 2) If we extend our basis search in all possible invertible linear transformations in $R^n$, then the best basis in statistical independence differs from the one in sparsity; 3) In either of the above, the best basis in statistical independence is not unique, and there even exist those which make the inputs completely dense; 4) There is no linear invertible transformation that achieves the true statistical independence for $n > 2$.
                    • Article
                    • Peer Reviewed
                    UC Davis Previously Published Works (2017)
                    We propose methods to efficiently approximate and denoise signals sampled on the nodes of graphs using our overcomplete multiscale transforms/basis dictionaries for such graph signals: the hierarchical graph Laplacian eigen transform (HGLET) and the generalized Haar-Walsh transform (GHWT). These can be viewed as generalizations of the hierarchical discrete cosine transform and the Haar-Walsh wavelet packet transform, respectively, from regularly sampled signals to graph signals. Both of these transforms generate dictionaries containing an immense number of choosable bases, and in order to select a particular basis most suitable for a given task, we have generalized the best basis algorithm from classical signal processing. After briefly reviewing these transforms and the best basis algorithm, we precisely prove their efficiency in approximating graph signals belonging to discrete analogs of the space of Hölder continuous functions and the Besov spaces. Then, we validate their effectiveness with numerical experiments on real datasets, in which we compare them against other graph-based transforms. Building upon this approximation efficiency of our transforms, we devise a signal denoising method using the HGLET and GHWT and again compare against other transforms. Our results clearly demonstrate the superiority of our transforms over those other transforms in terms of both approximation and denoising.
                      Cover page: Efficient Approximation and Denoising of Graph Signals Using the Multiscale Basis Dictionaries
                      Top