Source author record

Zhiqiang Xu

Zhiqiang Xu appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

34works
18topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

34 published item(s)

preprint2026arXiv

Improving Enzyme Prediction with Chemical Reaction Equations by Hypergraph-Enhanced Knowledge Graph Embeddings

Predicting enzyme-substrate interactions has long been a fundamental problem in biochemistry and metabolic engineering. While existing methods could leverage databases of expert-curated enzyme-substrate pairs for models to learn from known pair interactions, the databases are often sparse, i.e., there are only limited and incomplete examples of such pairs, and also labor-intensive to maintain. This lack of sufficient training data significantly hinders the ability of traditional enzyme prediction models to generalize to unseen interactions. In this work, we try to exploit chemical reaction equations from domain-specific databases, given their easier accessibility and denser, more abundant data. However, interactions of multiple compounds, e.g., educts and products, with the same enzymes create complex relational data patterns that traditional models cannot easily capture. To tackle that, we represent chemical reaction equations as triples of (educt, enzyme, product) within a knowledge graph, such that we can take advantage of knowledge graph embedding (KGE) to infer missing enzyme-substrate pairs for graph completion. Particularly, in order to capture intricate relationships among compounds, we propose our knowledge-enhanced hypergraph model for enzyme prediction, i.e., Hyper-Enz, which integrates a hypergraph transformer with a KGE model to learn representations of the hyper-edges that involve multiple educts and products. Also, a multi-expert paradigm is introduced to guide the learning of enzyme-substrate interactions with both the proposed model and chemical reaction equations. Experimental results show a significant improvement, with up to a 88% relative improvement in average enzyme retrieval accuracy and 30% improvement in pair-level prediction compared to traditional models, demonstrating the effectiveness of our approach.

preprint2026arXiv

Return of Frustratingly Easy Unsupervised Video Domain Adaptation

Unsupervised video domain adaptation (UVDA) is a practical but under-explored problem. In this paper, we propose a frustratingly easy UVDA method, called MetaTrans. Specifically, MetaTrans adopts a concise learning objective that contains only two fundamental loss terms. Despite the simplicity of the learning objective, MetaTrans embodies an advanced UVDA idea, that is, handling the spatial and temporal divergence of cross-domain videos separately, through a subtle model architecture design. By implementing a temporal-static subtraction module, MetaTrans effectively removes spatial and temporal divergence. Extensive empirical evaluations, particularly on various cross-domain action recognition tasks, show substantial absolute adaptation performance enhancement and significantly superior relative performance gain compared with state-of-the-art UVDA baselines.

preprint2024arXiv

Interlacing Polynomial Method for the Column Subset Selection Problem

This paper investigates the spectral norm version of the column subset selection problem. Given a matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$ and a positive integer $k\leq\text{rank}(\mathbf{A})$, the objective is to select exactly $k$ columns of $\mathbf{A}$ that minimize the spectral norm of the residual matrix after projecting $\mathbf{A}$ onto the space spanned by the selected columns. We use the method of interlacing polynomials introduced by Marcus-Spielman-Srivastava to derive a new upper bound on the minimal approximation error. This new bound is asymptotically sharp when the matrix $\mathbf{A}\in\mathbb{R}^{n\times d}$ obeys a spectral power-law decay. The relevant expected characteristic polynomials can be written as an extension of the expected polynomial for the restricted invertibility problem, incorporating two extra variable substitution operators. Finally, we propose a deterministic polynomial-time algorithm that achieves this error bound up to a computational error.

preprint2022arXiv

Local Differential Privacy for Belief Functions

In this paper, we propose two new definitions of local differential privacy for belief functions. One is based on Shafer's semantics of randomly coded messages and the other from the perspective of imprecise probabilities. We show that such basic properties as composition and post-processing also hold for our new definitions. Moreover, we provide a hypothesis testing framework for these definitions and study the effect of "don't know" in the trade-off between privacy and utility in discrete distribution estimation.

preprint2022arXiv

No existence of linear algorithm for Fourier phase retrieval

Fourier phase retrieval, which seeks to reconstruct a signal from its Fourier magnitude, is of fundamental importance in fields of engineering and science. In this paper, we give a theoretical understanding of algorithms for Fourier phase retrieval. Particularly, we show if there exists an algorithm which could reconstruct an arbitrary signal ${\mathbf x}\in {\mathbb C}^N$ in $ \mbox{Poly}(N) \log(1/ε)$ time to reach $ε$-precision from its magnitude of discrete Fourier transform and its initial value $x(0)$, then $\mathcal{ P}=\mathcal{NP}$. This demystifies the phenomenon that, although almost all signals are determined uniquely by their Fourier magnitude with a prior conditions, there is no algorithm with theoretical guarantees being proposed over the past few decades. Our proofs employ the result in computational complexity theory that Product Partition problem is NP-complete in the strong sense.

preprint2022arXiv

Strong convexity of affine phase retrieval

The recovery of a signal from the intensity measurements with some entries being known in advance is termed as {\em affine phase retrieval}. In this paper, we prove that a natural least squares formulation for the affine phase retrieval is strongly convex on the entire space under some mild conditions, provided the measurements are complex Gaussian random vecotrs and the measurement number $m \gtrsim d \log d$ where $d$ is the dimension of signals. Based on the result, we prove that the simple gradient descent method for the affine phase retrieval converges linearly to the target solution with high probability from an arbitrary initial point. These results show an essential difference between the affine phase retrieval and the classical phase retrieval, where the least squares formulations for the classical phase retrieval are non-convex.

preprint2021arXiv

Graph Sparsification by Universal Greedy Algorithms

Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications, such as simplification of social networks, least squares problems, numerical solution of symmetric positive definite linear systems and etc. In this paper, inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit (OMP), we introduce a deterministic, greedy edge selection algorithm called universal greedy approach (UGA) for graph sparsification. For a general spectral sparsification problem, e.g., positive subset selection problem from a set of $m$ vectors from $\mathbb{R}^n$, we propose a nonnegative UGA algorithm which needs $O(mn^2+ n^3/ε^2)$ time to find a $\frac{1+ε/β}{1-ε/β}$-spectral sparsifier with positive coefficients with sparsity $\le\lceil\frac{n}{ε^2}\rceil$, where $β$ is the ratio between the smallest length and largest length of the vectors. The convergence of the nonnegative UGA algorithm will be established. For the graph sparsification problem, another UGA algorithm will be proposed which can output a $\frac{1+O(ε)}{1-O(ε)}$-spectral sparsifier with $\lceil\frac{n}{ε^2}\rceil$ edges in $O(m+n^2/ε^2)$ time from a graph with $m$ edges and $n$ vertices under some mild assumptions. This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for. The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear, i.e. $O(m^{1+o(1)})$ for some $o(1)=O(\frac{(\log\log(m))^{2/3}}{\log^{1/3}(m)})$. Finally, extensive experimental results, including applications to graph clustering and least squares regression, show the effectiveness of proposed approaches.

preprint2020arXiv

Bounds on antipodal spherical designs with few angles

A finite subset $X$ on the unit sphere $\mathbb{S}^{d-1}$ is called an $s$-distance set with strength $t$ if its angle set $A(X):=\{\langle \mathbf{x},\mathbf{y}\rangle : \mathbf{x},\mathbf{y}\in X,\mathbf{x}\neq\mathbf{y} \}$ has size $s$, and $X$ is a spherical $t$-design but not a spherical $(t+1)$-design. In this paper, we consider to estimate the maximum size of such antipodal set for small $s$. First, we improve the known bound on $|X|$ for each even integer $s\in[\frac{t+5}{2}, t+1]$ when $t\geq 3$. We next focus on two special cases: $s=3,\ t=3$ and $s=4,\ t=5$. Estimating the size of $X$ for these two cases is equivalent to estimating the size of real equiangular tight frames (ETFs) and Levenstein-equality packings, respectively. We first improve the previous estimate on the size of real ETFs and Levenstein-equality packings. This in turn gives a bound on $|X|$ when $s=3,\ t=3$ and $s=4,\ t=5$, respectively.

preprint2020arXiv

Subset Selection for Matrices with Fixed Blocks

Subset selection for matrices is the task of extracting a column sub-matrix from a given matrix $B\in\mathbb{R}^{n\times m}$ with $m>n$ such that the pseudoinverse of the sampled matrix has as small Frobenius or spectral norm as possible. In this paper, we consider a more general problem of subset selection for matrices that allows a block to be fixed at the beginning. Under this setting, we provide a deterministic method for selecting a column sub-matrix from $B$. We also present a bound for both the Frobenius and spectral norms of the pseudoinverse of the sampled matrix, showing that the bound is asymptotically optimal. The main technology for proving this result is the interlacing families of polynomials developed by Marcus, Spielman, and Srivastava. This idea also results in a deterministic greedy selection algorithm that produces the sub-matrix promised by our result.

preprint2020arXiv

The minimizers of the $p$-frame potential

For any positive real number $p$, the $p$-frame potential of $N$ unit vectors $X:=\{\mathbf x_1,\ldots,\mathbf x_N\}\subset \mathbb R^d$ is defined as ${\rm FP}_{p,N,d}(X)=\sum_{i\neq j}|\langle \mathbf x_i,\mathbf x_j\rangle |^p$. In this paper, we focus on the special case $N=d+1$ and establish the unique minimizer of ${\rm FP}_{p,d+1,d}$ for $p\in (0,2)$. Our results completely solve the minimization problem of $p$-frame potential when $N=d+1$, which confirms a conjecture posed by Chen, Gonzales, Goodman, Kang and Okoudjou.

preprint2016arXiv

Generalized phase retrieval : measurement number, matrix recovery and beyond

In this paper, we develop a framework of generalized phase retrieval in which one aims to reconstruct a vector ${\mathbf x}$ in ${\mathbb R}^d$ or ${\mathbb C}^d$ through quadratic samples ${\mathbf x}^*A_1{\mathbf x}, \dots, {\mathbf x}^*A_N{\mathbf x}$. The generalized phase retrieval includes as special cases the standard phase retrieval as well as the phase retrieval by orthogonal projections. We first explore the connections among generalized phase retrieval, low-rank matrix recovery and nonsingular bilinear form. Motivated by the connections, we present results on the minimal measurement number needed for recovering a matrix that lies in a set $W\in {\mathbb C}^{d\times d}$. Applying the results to phase retrieval, we show that generic $d \times d$ matrices $A_1,\ldots, A_N$ have the phase retrieval property if $N\geq 2d-1$ in the real case and $N \geq 4d-4$ in the complex case for very general classes of $A_1,\ldots,A_N$, e.g. matrices with prescribed ranks or orthogonal projections. Our method also leads to a novel proof for the classical Stiefel-Hopf condition on nonsingular bilinear form. We also give lower bounds on the minimal measurement number required for generalized phase retrieval. For several classes of dimensions $d$ we obtain the precise values of the minimal measurement number. Our work unifies and enhances results from the standard phase retrieval, phase retrieval by projections and low-rank matrix recovery.

preprint2016arXiv

Phase Retrieval From the Magnitudes of Affine Linear Measurements

In this paper, we consider the phase retrieval problem in which one aims to recover a signal from the magnitudes of affine measurements. Let $\{{\mathbf a}_j\}_{j=1}^m \subset {\mathbb H}^d$ and ${\mathbf b}=(b_1, \ldots, b_m)^\top\in{\mathbb H}^m$, where ${\mathbb H}={\mathbb R}$ or ${\mathbb C}$. We say $\{{\mathbf a}_j\}_{j=1}^m$ and $\mathbf b$ are affine phase retrievable for ${\mathbb H}^d$ if any ${\mathbf x}\in{\mathbb H}^d$ can be recovered from the magnitudes of the affine measurements $\{|<{\mathbf a}_j,{\mathbf x}>+b_j|,\, 1\leq j\leq m\}$. We develop general framework for affine phase retrieval and prove necessary and sufficient conditions for $\{{\mathbf a}_j\}_{j=1}^m$ and $\mathbf b$ to be affine phase retrievable. We establish results on minimal measurements and generic measurements for affine phase retrieval as well as on sparse affine phase retrieval. In particular, we also highlight some notable differences between affine phase retrieval and the standard phase retrieval in which one aims to recover a signal $\mathbf x$ from the magnitudes of its linear measurements. In standard phase retrieval, one can only recover $\mathbf x$ up to a unimodular constant, while affine phase retrieval removes this ambiguity. We prove that unlike standard phase retrieval, the affine phase retrievable measurements $\{{\mathbf a}_j\}_{j=1}^m$ and $\mathbf b$ do not form an open set in ${\mathbb H}^{m\times d}\times {\mathbb H}^m$. Also in the complex setting, the standard phase retrieval requires $4d-O(\log_2d)$ measurements, while the affine phase retrieval only needs $m=3d$ measurements.

preprint2016arXiv

Stochastic Variance Reduced Riemannian Eigensolver

We study the stochastic Riemannian gradient algorithm for matrix eigen-decomposition. The state-of-the-art stochastic Riemannian algorithm requires the learning rate to decay to zero and thus suffers from slow convergence and sub-optimal solutions. In this paper, we address this issue by deploying the variance reduction (VR) technique of stochastic gradient descent (SGD). The technique was originally developed to solve convex problems in the Euclidean space. We generalize it to Riemannian manifolds and realize it to solve the non-convex eigen-decomposition problem. We are the first to propose and analyze the generalization of SVRG to Riemannian manifolds. Specifically, we propose the general variance reduction form, SVRRG, in the framework of the stochastic Riemannian gradient optimization. It's then specialized to the problem with eigensolvers and induces the SVRRG-EIGS algorithm. We provide a novel and elegant theoretical analysis on this algorithm. The theory shows that a fixed learning rate can be used in the Riemannian setting with an exponential global convergence rate guaranteed. The theoretical results make a significant improvement over existing studies, with the effectiveness empirically verified.

preprint2015arXiv

Robustness Properties of Dimensionality Reduction with Gaussian Random Matrices

In this paper we study the robustness properties of dimensionality reduction with Gaussian random matrices having arbitrarily erased rows. We first study the robustness property against erasure for the almost norm preservation property of Gaussian random matrices by obtaining the optimal estimate of the erasure ratio for a small given norm distortion rate. As a consequence, we establish the robustness property of Johnson-Lindenstrauss lemma and the robustness property of restricted isometry property with corruption for Gaussian random matrices. Secondly, we obtain a sharp estimate for the optimal lower and upper bounds of norm distortion rates of Gaussian random matrices under a given erasure ratio. This allows us to establish the strong restricted isometry property with the almost optimal RIP constants, which plays a central role in the study of phaseless compressed sensing.

preprint2015arXiv

Stable Signal Recovery from Phaseless Measurements

The aim of this paper is to study the stability of the $\ell_1$ minimization for the compressive phase retrieval and to extend the instance-optimality in compressed sensing to the real phase retrieval setting. We first show that the $m={\mathcal O}(k\log(N/k))$ measurements is enough to guarantee the $\ell_1$ minimization to recover $k$-sparse signals stably provided the measurement matrix $A$ satisfies the strong RIP property. We second investigate the phaseless instance-optimality with presenting a null space property of the measurement matrix $A$ under which there exists a decoder $Δ$ so that the phaseless instance-optimality holds. We use the result to study the phaseless instance-optimality for the $\ell_1$ norm. The results build a parallel for compressive phase retrieval with the classical compressive sensing.

preprint2015arXiv

The minimal measurement number for low-rank matrices recovery

The paper presents several results that address a fundamental question in low-rank matrices recovery: how many measurements are needed to recover low rank matrices? We begin by investigating the complex matrices case and show that $4nr-4r^2$ generic measurements are both necessary and sufficient for the recovery of rank-$r$ matrices in $\C^{n\times n}$ by algebraic tools. Thus, we confirm a conjecture which is raised by Eldar, Needell and Plan for the complex case. We next consider the real case and prove that the bound $4nr-4r^2$ is tight provided $n=2^k+r, k\in \Z_+$. Motivated by Vinzant's work, we construct $11$ matrices in $\R^{4\times 4}$ by computer random search and prove they define injective measurements on rank-$1$ matrices in $\R^{4\times 4}$. This disproves the conjecture raised by Eldar, Needell and Plan for the real case. Finally, we use the results in this paper to investigate the phase retrieval by projection and show fewer than $2n-1$ orthogonal projections are possible for the recovery of $x\in \R^n$ from the norm of them.

preprint2014arXiv

A strong restricted isometry property, with an application to phaseless compressed sensing

The many variants of the restricted isometry property (RIP) have proven to be crucial theoretical tools in the fields of compressed sensing and matrix completion. The study of extending compressed sensing to accommodate phaseless measurements naturally motivates a strong notion of restricted isometry property (SRIP), which we develop in this paper. We show that if $A \in \mathbb{R}^{m\times n}$ satisfies SRIP and phaseless measurements $|Ax_0| = b$ are observed about a $k$-sparse signal $x_0 \in \mathbb{R}^n$, then minimizing the $\ell_1$ norm subject to $ |Ax| = b $ recovers $x_0$ up to multiplication by a global sign. Moreover, we establish that the SRIP holds for the random Gaussian matrices typically used for standard compressed sensing, implying that phaseless compressed sensing is possible from $O(k \log (n/k))$ measurements with these matrices via $\ell_1$ minimization over $|Ax| = b$. Our analysis also yields an erasure robust version of the Johnson-Lindenstrauss Lemma.

preprint2014arXiv

Multivariate discrete least-squares approximations with a new type of collocation grid

In this work, we discuss the problem of approximating a multivariate function by discrete least squares projection onto a polynomial space using a specially designed deterministic point set. The independent variables of the function are assumed to be random variables, stemming from the motivating application of Uncertainty Quantification (UQ). Our deterministic points are inspired by a theorem due to André Weil. We first work with the Chebyshev measure and consider the approximation in Chebyshev polynomial spaces. We prove the stability and an optimal convergence estimate, provided the number of points scales quadratically with the dimension of the polynomial space. A possible application for quantifying \textit{epistemic} uncertainties is then discussed. We show that the point set asymptotically equidistributes to the product-Chebyshev measure, allowing us to propose a weighted least squares framework, and extending our method to more general polynomial approximations. Numerical examples are given to confirm the theoretical results. It is shown that the performance of our deterministic points is similar to that of randomly-generated points. However our construction, being deterministic, does not suffer from probabilistic qualifiers on convergence results. (E.g., convergence "with high probability".)

preprint2014arXiv

The lower bound of the PCM quantization error in high dimension

In this note, we investigate the performance of the PCM scheme with linear quantization rule for quantizing unit-norm tight frame expansions for ${\mathbb R}^d$ without the White Noise Hypothesis. In \cite{WX}, Wang and Xu showed that for asymptotically equidistributed unit-norm tight frame the PCM quantization error has an upper bound ${\mathcal O}(δ^{(d+1)/2})$ and they conjecture the upper bound is sharp. In this note, we confirm the conjecture with employing the asymptotic estimate of the Bessel functions.

preprint2013arXiv

Compressed Sensing Matrices from Fourier Matrices

The class of Fourier matrices is of special importance in compressed sensing (CS). This paper concerns deterministic construction of compressed sensing matrices from Fourier matrices. By using Katz' character sum estimation, we are able to design a deterministic procedure to select rows from a Fourier matrix to form a good compressed sensing matrix for sparse recovery. The sparsity bound in our construction is similar to that of binary CS matrices constructed by DeVore which greatly improves previous results for CS matrices from Fourier matrices. Our approach also provides more flexibilities in terms of the dimension of CS matrices. As a consequence, our construction yields an approximately mutually unbiased bases from Fourier matrices which is of particular interest to quantum information theory. This paper also contains a useful improvement to Katz' character sum estimation for quadratic extensions, with an elementary and transparent proof. Some numerical examples are included.

preprint2013arXiv

On sparse interpolation and the design of deterministic interpolation points

In this paper, we build up a framework for sparse interpolation. We first investigate the theoretical limit of the number of unisolvent points for sparse interpolation under a general setting and try to answer some basic questions of this topic. We also explore the relation between classical interpolation and sparse interpolation. We second consider the design of the interpolation points for the $s$-sparse functions in high dimensional Chebyshev bases, for which the possible applications include uncertainty quantification, numerically solving stochastic or parametric PDEs and compressed sensing. Unlike the traditional random sampling method, we present in this paper a deterministic method to produce the interpolation points, and show its performance with $\ell_1$ minimization by analyzing the mutual incoherence of the interpolation matrix. Numerical experiments show that the deterministic points have a similar performance with that of the random points.

preprint2013arXiv

On the $\ell_1$-Norm Invariant Convex k-Sparse Decomposition of Signals

Inspired by an interesting idea of Cai and Zhang, we formulate and prove the convex $k$-sparse decomposition of vectors which is invariant with respect to $\ell_1$ norm. This result fits well in discussing compressed sensing problems under RIP, but we believe it also has independent interest. As an application, a simple derivation of the RIP recovery condition $δ_k+θ_{k,k} < 1$ is presented.

preprint2013arXiv

One-Bit Compressed Sensing by Greedy Algorithms

Sign truncated matching pursuit (STrMP) algorithm is presented in this paper. STrMP is a new greedy algorithm for the recovery of sparse signals from the sign measurement, which combines the principle of consistent reconstruction with orthogonal matching pursuit (OMP). The main part of STrMP is as concise as OMP and hence STrMP is simple to implement. In contrast to previous greedy algorithms for one-bit compressed sensing, STrMP only need to solve a convex and unconstraint subproblem at each iteration. Numerical experiments show that STrMP is fast and accurate for one-bit compressed sensing compared with other algorithms.

preprint2013arXiv

Phase Retrieval for Sparse Signals

The aim of this paper is to build up the theoretical framework for the recovery of sparse signals from the magnitude of the measurement. We first investigate the minimal number of measurements for the success of the recovery of sparse signals without the phase information. We completely settle the minimality question for the real case and give a lower bound for the complex case. We then study the recovery performance of the $\ell_1$ minimization. In particular, we present the null space property which, to our knowledge, is the first sufficient and necessary condition for the success of $\ell_1$ minimization for $k$-sparse phase retrievable.

preprint2013arXiv

The performance of orthogonal multi-matching pursuit under RIP

The orthogonal multi-matching pursuit (OMMP) is a natural extension of orthogonal matching pursuit (OMP). We denote the OMMP with the parameter $M$ as OMMP(M) where $M\geq 1$ is an integer. The main difference between OMP and OMMP(M) is that OMMP(M) selects $M$ atoms per iteration, while OMP only adds one atom to the optimal atom set. In this paper, we study the performance of orthogonal multi-matching pursuit (OMMP) under RIP. In particular, we show that, when the measurement matrix A satisfies $(9s, 1/10)$-RIP, there exists an absolutely constant $M_0\leq 8$ so that OMMP(M_0) can recover $s$-sparse signal within $s$ iterations. We furthermore prove that, for slowly-decaying $s$-sparse signal, OMMP(M) can recover s-sparse signal within $O(\frac{s}{M})$ iterations for a large class of $M$. In particular, for $M=s^a$ with $a\in [0,1/2]$, OMMP(M) can recover slowly-decaying $s$-sparse signal within $O(s^{1-a})$ iterations. The result implies that OMMP can reduce the computational complexity heavily.

preprint2012arXiv

On B-spline framelets derived from the unitary extension principle

Spline wavelet tight frames of Ron-Shen have been used widely in frame based image analysis and restorations. However, except for the tight frame property and the approximation order of the truncated series, there are few other properties of this family of spline wavelet tight frames to be known. This paper is to present a few new properties of this family that will provide further understanding of it and, hopefully, give some indications why it is efficient in image analysis and restorations. In particular, we present a recurrence formula of computing generators of higher order spline wavelet tight frames from the lower order ones. We also represent each generator of spline wavelet tight frames as certain order of derivative of some univariate box spline. With this, we further show that each generator of sufficiently high order spline wavelet tight frames is close to a right order of derivative of a properly scaled Gaussian function. This leads to the result that the wavelet system generated by a finitely many consecutive derivatives of a properly scaled Gaussian function forms a frame whose frame bounds can be almost tight.

preprint2011arXiv

A remark about orthogonal matching pursuit algorithm

In this note, we investigate the theoretical properties of Orthogonal Matching Pursuit (OMP), a class of decoder to recover sparse signal in compressed sensing. In particular, we show that the OMP decoder can give $(p,q)$ instance optimality for a large class of encoders with $1\leq p\leq q \leq 2$ and $(p,q)\neq (2,2)$. We also show that, if the encoding matrix is drawn from an appropriate distribution, then the OMP decoder is $(2,2)$ instance optimal in probability.

preprint2011arXiv

Deterministic Sampling of Sparse Trigonometric Polynomials

One can recover sparse multivariate trigonometric polynomials from few randomly taken samples with high probability (as shown by Kunis and Rauhut). We give a deterministic sampling of multivariate trigonometric polynomials inspired by Weil's exponential sum. Our sampling can produce a deterministic matrix satisfying the statistical restricted isometry property, and also nearly optimal Grassmannian frames. We show that one can exactly reconstruct every $M$-sparse multivariate trigonometric polynomial with fixed degree and of length $D$ from the determinant sampling $X$, using the orthogonal matching pursuit, and $# X$ is a prime number greater than $(M\log D)^2$. This result is almost optimal within the $(\log D)^2 $ factor. The simulations show that the deterministic sampling can offer reconstruction performance similar to the random sampling.

preprint2011arXiv

The Performance of PCM Quantization Under Tight Frame Representations

In this paper, we study the performance of the PCM scheme with linear quantization rule for quantizing finite unit-norm tight frame expansions for $\R^d$ and derive the PCM quantization error without the White Noise Hypothesis. We prove that for the class of unit norm tight frames derived from uniform frame paths the quantization error has an upper bound of $O(δ^{3/2})$ regardless of the frame redundancy. This is achieved using some of the techniques developed by Güntürk in his study of Sigma-Delta quantization. Using tools of harmonic analysis we show that this upper bound is sharp for $d=2$. A consequence of this result is that, unlike with Sigma-Delta quantization, the error for PCM quantization in general does not diminish to zero as one increases the frame redundancy. We extend the result to high dimension and show that the PCM quantization error has an upper bound $O(δ^{(d+1)/2})$ for asymptopitcally equidistributed unit-norm tight frame of $\R^{d}$.

preprint2011arXiv

The Regularity of Refinable Functions

The regularity of refinable functions has been studied extensively in the past. A classical result by Daubechies and Lagarias states that a compactly supported refinable function in $\R$ of finite mask with integer dilation and translations cannot be in $C^\infty$. A bound on the regularity based on the eigenvalues of certain matrices associated with the refinement equation is also given. Surprisingly this fundamental classical result has not been proved in the more general settings, such as in higher dimensions or when the dilation is not an integer. In this paper we extend this classical result to the most general setting for arbitrary dimension, dilation and translations.

preprint2010arXiv

Application of multivariate splines to discrete mathematics

Using methods developed in multivariate splines, we present an explicit formula for discrete truncated powers, which are defined as the number of non-negative integer solutions of linear Diophantine equations. We further use the formula to study some classical problems in discrete mathematics as follows. First, we extend the partition function of integers in number theory. Second, we exploit the relation between the relative volume of convex polytopes and multivariate truncated powers and give a simple proof for the volume formula for the Pitman-Stanley polytope. Third, an explicit formula for the Ehrhart quasi-polynomial is presented.

preprint2010arXiv

Hierarchical zonotopal spaces

Zonotopal algebra interweaves algebraic, geometric and combinatorial properties of a given linear map X. Of basic significance in this theory is the fact that the algebraic structures are derived from the geometry (via a non-linear procedure known as "the least map"), and that the statistics of the algebraic structures (e.g., the Hilbert series of various polynomial ideals) are combinatorial, i.e., computable using a simple discrete algorithm known as "the valuation function". On the other hand, the theory is somewhat rigid since it deals, for the given X, with exactly two pairs each of which is made of a nested sequence of three ideals: an external ideal (the smallest), a central ideal (the middle), and an internal ideal (the largest). In this paper we show that the fundamental principles of zonotopal algebra as described in the previous paragraph extend far beyond the setup of external, central and internal ideals by building a whole hierarchy of new combinatorially defined zonotopal spaces.

preprint2010arXiv

Multivariate Splines and Polytopes

In this paper, we use multivariate splines to investigate the volume of polytopes. We first present an explicit formula for the multivariate truncated power, which can be considered as a dual version of the famous Brion's formula for the volume of polytopes. We also prove that the integration of polynomials over polytopes can be dealt with by the multivariate truncated power. Moreover, we show that the volume of the cube slicing can be considered as the maximum value of the box spline. Based on this connection, we give a simple proof for Good's conjecture, which has been settled by probability methods.

preprint2009arXiv

Subspace modelling for structured noise suppression

The problem of structured noise suppression is addressed by i)modelling the subspaces hosting the components of the signal conveying the information and ii)applying a non-extensive nonlinear technique for effecting the right separation. Although the approach is applicable to all situations satisfying the hypothesis of the proposed framework, this work is motivated by a particular scenario, namely, the cancellation of low frequency noise in broadband seismic signals.