Jie Ding
Associate Professor @UMN
Journal paper
Publication Types:
Towards Understanding Variation-Constrained Deep Neural Networks
Abstract:
Multi-layer feedforward networks have been used to approximate a wide range of nonlinear functions. A fundamental problem is understanding the generalizability of a neural network model through its statistical risk, or the expected test error. In particular, it is important to understand the phenomenon that overparameterized deep neural networks may not suffer from overfitting when the number of neurons and learning parameters rapidly grow with n or even surpass n. In this paper, we show that a class of variation-constrained regression neural networks, with arbitrary width, can achieve a near-parametric rate n^{−1/2+δ} for an arbitrarily small positive constant δ. It is equivalent to n^{−1+2δ} under the mean squared error. This rate is also observed from numerical experiments. The result provides an insight into the benign overparameterization phenomenon. It indicates that the number of trainable parameters may not be a suitable complexity measure as often perceived for classical regression models. We also discuss the convergence rate regarding other network parameters, including the input dimension, network layer, and coefficient norm.
Keywords:
Complexity theory
Deep learning theory
Statistical convergence analysis
Provable Identifiability of Two-Layer ReLU Neural Networks via LASSO Regularization
Abstract:
LASSO regularization is a popular regression tool to enhance the prediction accuracy of statistical models by performing variable selection through the l1 penalty, initially formulated for the linear model and its variants. In this paper, the territory of LASSO is extended to the neural network model, a fashionable and powerful nonlinear regression model. Specifically, given a neural network whose output y depends only on a small subset of input x, denoted by S, we prove that the LASSO estimator can stably reconstruct the neural network and identify S when the number of samples scales logarithmically with the input dimension. This challenging regime has been well understood for linear models while barely studied for neural networks. Our theory lies in an extended Restricted Isometry Property (RIP)-based analysis framework for two-layer ReLU neural networks, which may be of independent interest to other LASSO or neural network settings. Based on the result, we advocate a neural network-based variable selection method. Experiments on simulated and real-world datasets show promising performance of the variable selection approach compared with existing techniques.
Keywords:
Lasso
Identifiability
Neural network
Nonlinear regression
Variable selection
Parallel Assisted Learning
Abstract:
In the era of big data, a population’s multimodal data are often collected and preserved by different business and government entities. These entities often have their local machine learning data, models, and tasks that they cannot share with others. Meanwhile, an entity often needs to seek assistance from others to enhance its learning quality without sharing proprietary information. How can an entity be assisted while it is assisting others? We develop a general method called parallel assisted learning (PAL) that applies to the context where entities perform supervised learning and can collate their data according to a common data identifier. Under the PAL mechanism, a learning entity that receives assistance is obligated to assist others without the need to reveal any entity’s local data, model, and learning objective. Consequently, each entity can significantly improve its particular task. The applicability of the proposed approach is demonstrated by data experiments.
Keywords:
Assisted learning
Incentive
Information Criteria for Model Selection
Abstract:
The rapid development of modeling techniques has brought many opportunities for data-driven discovery and prediction. However, this also leads to the challenge of selecting the most appropriate model for any particular data task. Information criteria, such as the Akaike information criterion (AIC) and Bayesian information criterion (BIC), have been developed as a general class of model selection methods with profound connections with foundational thoughts in statistics and information theory. Many perspectives and theoretical justifications have been developed to understand when and how to use information criteria, which often depend on particular data circumstances. This review article will revisit information criteria by summarizing their key concepts, evaluation metrics, fundamental properties, interconnections, recent advancements, and common misconceptions to enrich the understanding of model selection in general.
Keywords:
Modeling Methods
Model Selection
Information Theoretic Methods
Explainable multi-task learning for multi-modality biological data analysis
Abstract:
Current biotechnologies can simultaneously measure multiple high-dimensional modalities (e.g., RNA, DNA accessibility, and protein) from the same cells. A combination of different analytical tasks (e.g., multi-modal integration and cross-modal analysis) is required to comprehensively understand such data, inferring how gene regulation drives biological diversity and functions. However, current analytical methods are designed to perform a single task, only providing a partial picture of the multi-modal data. Here, we present UnitedNet, an explainable multi-task deep neural network capable of integrating different tasks to analyze single-cell multi-modality data. Applied to various multi-modality datasets (e.g., Patch-seq, multiome ATAC + gene expression, and spatial transcriptomics), UnitedNet demonstrates similar or better accuracy in multi-modal integration and cross-modal prediction compared with state-of-the-art methods. Moreover, by dissecting the trained UnitedNet with the explainable machine learning algorithm, we can directly quantify the relationship between gene expression and other modalities with cell-type specificity. UnitedNet is a comprehensive end-to-end framework that could be broadly applicable to single-cell multi-modality biology. This framework has the potential to facilitate the discovery of cell-type-specific regulation kinetics across transcriptomics and other modalities.
Keywords:
AI for healthcare
Deep learning
Single-cell biology
Assisted Learning for Organizations with Limited Imbalanced Data
Abstract:
In the era of big data, many big organizations are integrating machine learning into their work pipelines to facilitate data analysis. However, the performance of their trained models is often restricted by limited and imbalanced data available to them. In this work, we develop an assisted learning framework for assisting organizations to improve their learning performance. The organizations have sufficient computation resources but are subject to stringent data-sharing and collaboration policies. Their limited imbalanced data often cause biased inference and sub-optimal decision-making. In assisted learning, an organizational learner purchases assistance service from an external service provider and aims to enhance its model performance within only a few assistance rounds. We develop effective stochastic training algorithms for both assisted deep learning and assisted reinforcement learning. Different from existing distributed algorithms that need to transmit gradients or models frequently, our framework allows the learner to only occasionally share information with the service provider, but still, obtain a model that achieves near-oracle performance as if all the data were centralized.
Keywords:
Assisted Learning
Imbalanced Data
Abstract:
In many applications, we have access to the complete dataset but are only interested in the prediction of a particular region of predictor variables. A standard approach is to find the globally best modeling method from a set of candidate methods. However, it is perhaps rare in reality that one candidate method is uniformly better than the others. A natural approach for this scenario is to apply a weighted L2 loss in performance assessment to reflect the region-specific interest. We propose targeted cross-validation (TCV) to select models or procedures based on a general weighted L2 loss. We show that the TCV is consistent in selecting the best performing candidate under the weighted L2 loss. Experimental studies are used to demonstrate the use of TCV and its potential advantage over the global CV or the approach of using only local data for modeling a local region.
Previous investigations on CV have relied on the condition that when the sample size is large enough, the ranking of two candidates stays the same. However, in many applications with the setup of changing data-generating processes or highly adaptive modeling methods, the relative performance of the methods is not static as the sample size varies. Even with a fixed data-generating process, it is possible that the ranking of two methods switches infinitely many times. In this work, we broaden the concept of selection consistency by allowing the best candidate to switch as the sample size varies, and then establish the consistency of the TCV. This flexible framework can be applied to high-dimensional and complex machine learning scenarios where the relative performances of modeling procedures are dynamic.
Keywords:
Consistency
Cross-validation
Model selection
Regression
Regression with Set-Valued Categorical Predictors
Abstract:
We address the regression problem with a new form of data that arises from data privacy applications. Instead of point values, the observed explanatory variables are subsets containing each individual’s original value. The classical regression analyses such as least squares are not applicable since the set-valued predictors only carry partial information about the original values. We propose a computationally efficient subset least squares method to perform regression for such data. We establish upper bounds of the prediction loss and risk in terms of the subset structure, the model structure, and the data dimension. The error rates are shown to be optimal under some common situations. Furthermore, we develop a model selection method to identify the most appropriate model for prediction. Experiment results on both simulated and real-world datasets demonstrate the promising performance of the proposed method.
Keywords:
Model selection
Regression
Set-valued data
Meta Clustering for Collaborative Learning
Abstract:
An emerging number of learning scenarios involve a set of learners or analysts, each equipped with a unique dataset and algorithm, who may collaborate to enhance their learning performance. From a particular learner’s perspective, a careless collaboration with task-irrelevant other learners is likely to incur modeling error. A crucial challenge is to search for the most appropriate collaborators so that their data and modeling resources can be effectively leveraged. Motivated by this, we propose to study the problem of ‘meta clustering,’ where the goal is to identify subsets of relevant learners whose collaboration will improve each learner’s performance. In particular, we study the scenario where each learner performs a supervised regression, and the meta clustering aims to categorize the underlying supervised relations (between responses and predictors) instead of the private raw data. We propose a general method named Select-Exchange-Cluster (SEC) for performing such a clustering. Our method is computationally efficient as it does not require each learner to exchange their raw data. We prove that the SEC method can accurately cluster the learners into appropriate collaboration sets according to their underlying regression functions. Synthetic and real data examples show the desired performance and wide applicability of the SEC to various learning tasks.
Keywords:
Distributed computing
Fairness
Meta clustering
Regression
Interval Privacy: A Framework for Privacy-Preserving Data Collection
Abstract:
Keywords:
Data collection
Data privacy
Interval mechanism
Local privacy
L1 Regularization in Two-Layer Neural Networks
Abstract:
A crucial problem of neural networks is to select an architecture that strikes appropriate tradeoffs between underfitting and overfitting. This work shows that ℓ1 regularizations for two-layer neural networks can control the generalization error and sparsify the input dimension. In particular, with an appropriate ℓ1 regularization on the output layer, the network can produce a tight statistical risk. Moreover, an appropriate ℓ1 regularization on the input layer leads to a risk bound that does not involve the input data dimension. The results also indicate that training a wide neural network with a suitable regularization provides an alternative bias-variance tradeoff to selecting from a candidate set of neural networks. Our analysis is based on a new integration of dimension-based and norm-based complexity analysis to bound the generalization error.
Keywords:
Generalization error
Regularization
Statistical risk
Two-layer neural network
On Statistical Efficiency in Learning
Abstract:
A central issue of many statistical learning problems is to select an appropriate model from a set of candidate models. Large models tend to inflate the variance (e.g., overfitting), while small models tend to cause biases (e.g., underfitting) for a given fixed dataset. In this work, we address the critical challenge of model selection to strike a balance between model fitting and model complexity, thus gaining reliable predictive power. We consider the task of approaching the theoretical limit of statistical learning, meaning that the selected model has the predictive performance that is as good as the best possible model given a class of potentially misspecified candidate models.
We propose a generalized notion of Takeuchi’s information criterion and prove that the proposed method can asymptotically achieve the optimal out-sample prediction loss under reasonable assumptions. It is the first proof of the asymptotic property of Takeuchi’s information criterion to our best knowledge. Our proof applies to a wide variety of nonlinear models, loss functions, and high dimensionality (in the sense that the models’ complexity can grow with sample size). The proposed method can be used as a computationally efficient surrogate for leave-one-out cross-validation. Moreover, for modeling streaming data, we propose an online algorithm that sequentially expands the model complexity to enhance selection stability and reduce computation cost. Experimental studies show that the proposed method has desirable predictive power and much less computational cost than some popular methods.
Keywords:
Cross-validation
Expert learning
Feature selection
Limit of learning
Model expansion
Model Linkage Selection for Cooperative Learning
Abstract:
Rapid developments in data collecting devices and computation platforms produce an emerging number of learners and data modalities in many scientific domains. We consider the setting in which each learner holds a pair of parametric statistical model and a specific data source, with the goal of integrating information across a set of learners to enhance the prediction accuracy of a specific learner. One natural way to integrate information is to build a joint model across a set of learners that shares common parameters of interest. However, the parameter sharing patterns across a set of learners are not known a priori. In this paper, we propose a novel framework for integrating information across a set of learners that is robust against model misspecification and misspecified parameter sharing patterns. The main crux is to sequentially incorporate additional learners that can enhance the prediction accuracy of an existing joint model based on user-specified parameter sharing patterns across a set of learners.
Keywords:
Data integration
Distributed learning
Model linkage selection
Is a Classification Procedure Good Enough?--A Goodness-of-Fit Assessment Tool for Classification Learning
Abstract:
In recent years, many non-traditional classification methods, such as Random Forest, Boosting, and neural network, have been widely used in applications. Their performance is typically measured in terms of classification accuracy. While the classification error rate and the like are important, they do not address a fundamental question: Is the classification method underfitted? To our best knowledge, there is no existing method that can assess the goodness-of-fit of a general classification procedure. Indeed, the lack of a parametric assumption makes it challenging to construct proper tests. To overcome this difficulty, we propose a methodology called BAGofT that splits the data into a training set and a validation set. First, the classification procedure to assess is applied to the training set, which is also used to adaptively find a data grouping that reveals the most severe regions of underfitting. Then, based on this grouping, we calculate a test statistic by comparing the estimated success probabilities and the actual observed responses from the validation set. The data splitting guarantees that the size of the test is controlled under the null hypothesis, and the power of the test goes to one as the sample size increases under the alternative hypothesis. For testing parametric classification models, the BAGofT has a broader scope than the existing methods since it is not restricted to specific parametric models (e.g., logistic regression). Extensive simulation studies show the utility of the BAGofT when assessing general classification procedures and its strengths over some existing methods when testing parametric classification models.
Keywords:
Goodness-of-fit test
Cassification procedure
Adaptive partition
Evolutionary Spectra Based on the Multitaper Method with Application to Stationarity Test
Abstract:
In this work, we propose a new inference procedure for understanding non-stationary processes under the framework of evolutionary spectra developed by Priestley. Among various frameworks of non-stationary modeling, the distinguishing feature of the evolutionary spectra is its focus on the physical meaning of frequency. The classical estimate of the evolutionary spectral density is based on a double-window technique consisting of a short-time Fourier transform and a smoothing. However, smoothing is known to suffer from the so-called bias leakage problem. By incorporating Thomson’s multitaper method that was originally designed for stationary processes, we propose an improved estimate of the evolutionary spectral density and analyze its bias/variance/resolution tradeoff. As an application of the new estimate, we further propose a non-parametric rank-based stationarity test and provide various experimental studies.
Keywords:
Non-stationary processes
Evolutionary spectra
Spectral analysis
Multitaper method
Stationarity test
Bayesian Model Comparison with the Hyvärinen Score: Computation and Consistency
Abstract:
The Bayes factor is a widely used criterion in model comparison, and its logarithm is a difference of out-of-sample predictive scores under the logarithmic scoring rule. However, when some of the candidate models involve vague priors on their parameters, the log-Bayes factor features an arbitrary additive constant that hinders its interpretation. As an alternative, we consider model comparison using the Hyvärinen score. We propose a method to consistently estimate this score for parametric models, using sequential Monte Carlo methods. We show that this score can be estimated for models with tractable likelihoods as well as nonlinear non-Gaussian state-space models with intractable likelihoods. We prove the asymptotic consistency of this new model selection criterion under strong regularity assumptions in the case of non-nested models, and we provide qualitative insights for the nested case. We also use existing characterizations of proper scoring rules on discrete spaces to extend the Hyvärinen score to discrete observations. Our numerical illustrations include Lévy-driven stochastic volatility models and diffusion models for population dynamics. Supplementary materials for this article are available online.
Keywords:
Bayes factor
Noninformative prior
Model selection
Sequential Monte Carlo
State-space model
Asymptotically Optimal Prediction for Time-Varying Data Generating Processes
Abstract:
We develop a methodology (referred to as kinetic prediction) for predicting time series undergoing unknown changes in their data generating distributions. Based on Kolmogorov-Tikhomirov’s ε-entropy, we propose a concept called ε-predictability that quantifies the size of a model class (which can be parametric or nonparametric) and the maximal number of abrupt structural changes that guarantee the achievability of asymptotically optimal prediction. Moreover, for parametric distribution families, we extend the aforementioned kinetic prediction with discretized function spaces to its counterpart with continuous function spaces and propose a sequential Monte Carlo based implementation.
We also extend our methodology for predicting smoothly varying data generating distributions. Under reasonable assumptions, we prove that the average predictive performance converges almost surely to the oracle bound, which corresponds to the case that the data generating distributions are known in advance. The results also shed some light on the so-called “prediction-inference dilemma.” Various examples and numerical results are provided to demonstrate the wide applicability of our methodology.
Keywords:
Change points
Kinetic prediction
ε-entropy
Optimal prediction
Sequential Monte-Carlo
Smooth variations
Online tracking
Online Learning for Multimodal Data Fusion with Application to Object Recognition
Abstract:
We consider online multimodal data fusion, where the goal is to combine information from multiple modes to identify an element in a large dictionary. We address this problem in object recognition by focusing on tactile sensing as one of the modes. Using a tactile glove with seven sensors, various individuals grasp different objects to obtain 7-D time series, where each component represents the pressure sequence applied to one sensor. The pressure data of all objects is stored in a dictionary as a reference. The objective is to match a streaming vector time series from grasping an unknown object to a dictionary object. We propose an algorithm that may start with prior knowledge provided by other modes. Receiving pressure data sequentially, the algorithm uses a dissimilarity metric to modify the prior and form a probability distribution over the dictionary. When the dictionary objects are dissimilar in shape, we empirically show that our algorithm recognize the unknown object even with a uniform prior. If there exists a similar object to the unknown object in the dictionary, our algorithm needs the prior from other modes to detect the unknown object. Notably, our algorithm maintains a similar performance to standard offline classification techniques, such as support vector machine, with a significantly lower computational time.
Keywords:
Object recognition
Online learning
Tactile sensing
Model Selection Techniques--An Overview
Abstract:
In the era of big data, analysts usually explore various statistical models or machine-learning methods for observed data to facilitate scientific discoveries or gain predictive power. Whatever data and fitting procedures are employed, a crucial step is to select the most appropriate model or method from a set of candidates. Model selection is the central ingredient in data analysis for reliable and reproducible statistical inference or prediction, and thus it is central to scientific studies in such fields as ecology, economics, engineering, finance, political science, biology, and epidemiology.
There has been a long history of model selection techniques that arise from researches in statistics, information theory, and signal processing. A considerable number of methods have been proposed, following different philosophies and exhibiting varying performances. The purpose of this article is to provide a comprehensive overview of them in terms of their motivation, large sample performance, and applicability. We provide integrated and practically relevant discussions on the theoretical properties of the state-of-the-art model selection approach. We also share our thoughts on some controversial views on the practice of model selection.
Keywords:
Akaike information criterion
Bayesian information criterion
Bridge criterion
Cross-validation
Model preference
Bridging AIC and BIC: A New Criterion for Autoregression
Abstract:
To address order selection for an autoregressive model fitted to time series data, we propose a new information criterion. It has the benefits of the two well-known model selection techniques, the Akaike information criterion, and the Bayesian information criterion. When the data is generated from a finite order autoregression, the Bayesian information criterion is known to be consistent, and so is the new criterion. When the true order is infinity or suitably high with respect to the sample size, the Akaike information criterion is known to be efficient in the sense that its predictive performance is asymptotically equivalent to the best offered by the candidate models; in this case, the new criterion behaves in a similar manner. Different from the two classical criteria, the proposed criterion adaptively achieves either consistency or efficiency, depending on the underlying data generating process. In practice, where the observed time series is given without any prior information about the model specification, the proposed order selection criterion is more flexible and reliable compared with classical approaches. Numerical results are presented to demonstrate the adaptivity of the proposed technique when applied to various datasets.
Keywords:
Adaptivity
Akaike information criterion
Asymptotic efficiency
Bayesian information criterion
Bridge criterion
Consistency
Information criterion
Model selection
Analysis of Multistate Autoregressive Models
Abstract:
In this work, we consider the inference problem for a wide class of time-series models, referred to as multistate autoregressive models. The time series that we consider are composed of multiple epochs, each modeled by an autoregressive process. The number of epochs is unknown, and the transitions of states follow a Markov process of unknown order. We propose an inference strategy that enables reliable and efficient offline analysis of this class of time series. The inference is carried out through a three-step approach: detecting the structural changes of the time series using a recently proposed multiwindow algorithm, identifying each segment as a state and selecting the most appropriate number of states, and estimating the Markov source based upon the symbolic sequence obtained from previous steps. We provide theoretical results and algorithms in order to facilitate the inference procedure described above. We demonstrate the accuracy, efficiency, and wide applicability of the proposed algorithms via an array of experiments using synthetic and real-world data.
Keywords:
Multi-regime models
Prediction
Recurring patterns
Time series
SLANTS: Sequential Adaptive Nonlinear Modeling of Time Series
Abstract:
We propose a method for adaptive nonlinear sequential modeling of time series data. Data are modeled as a nonlinear function of past values corrupted by noise, and the underlying nonlinear function is assumed to be approximately expandable on a spline basis. We cast the modeling of data as finding a good fit representation in the linear span of a multidimensional spline basis and use a variant of l1 -penalty regularization in order to reduce the dimensionality of representation. Using adaptive filtering techniques, we design our online algorithm to automatically tune the underlying parameters based on the minimization of the regularized sequential prediction error. We demonstrate the generality and flexibility of the proposed approach on both synthetic and real-world datasets. Moreover, we analytically investigate the performance of our algorithm by obtaining both bounds on prediction errors and consistency in variable selection.
Keywords:
Adaptive filtering
Data prediction
Nonlinearity
Sequential modeling
Spline
Time series
Multiple Change Point Analysis: Fast Implementation and Strong Consistency
Abstract:
One of the main challenges in identifying structural changes in stochastic processes is to carry out analysis for time series with the dependency structure in a computationally tractable way. Another challenge is that the number of true change points is usually unknown, requiring a suitable model selection criterion to arrive at informative conclusions.
To address the first challenge, we model the data generating process as a segment-wise autoregression, which is composed of several segments (time epochs), each of which is modeled by an autoregressive model. We propose a multi-window method that is both effective and efficient for discovering the structural changes. The proposed approach was motivated by transforming a segment-wise autoregression into a multivariate time series that is asymptotically segment-wise independent and identically distributed. To address the second challenge, we derive theoretical guarantees for (almost surely) selecting the true number of change points of segment-wise independent multivariate time series. Specifically, under mild assumptions, we show that a Bayesian information criterion like criterion gives a strongly consistent selection of the optimal number of change points, while an Akaike information criterion like criterion cannot.
Finally, we demonstrate the theory and strength of the proposed algorithms by experiments on both synthetic- and real-world data, including the Eastern U.S. temperature data and the El Nino data. The experiment leads to some interesting discoveries about temporal variability of the summer-time temperature over the Eastern U.S. and about the most dominant factor of ocean influence on climate, which was also discovered by environmental scientists.
Keywords:
Change detection
Information criteria
Large deviation analysis
Strong consistency
Time series
Complementary Lattice Arrays for Coded Aperture Imaging
Abstract:
In this work, we propose the concept of complementary lattice arrays in order to enable a broader range of designs for coded aperture imaging systems. We provide a general framework and methods that generate richer and more flexible designs compared to the existing techniques. Besides this, we review and interpret the state-of-the-art uniformly redundant array designs, broaden the related concepts, and propose new design methods.
Keywords:
Combinatorial design
Complementary sequence
Imaging systems
X-ray coded apertures
Key Pre-distributions from Graph-Based Block Designs
Abstract:
With the development of wireless communication technologies that considerably contributed to wireless sensor networks (WSNs), we have witnessed ever-increasing WSN-based applications that induced a host of research activities in both academia and industry. Since most of the target WSN applications are very sensitive, the security issue is one of the major challenges in the deployment of WSN. One of the important building blocks in securing WSN is key management. Traditional key management solutions developed for other networks are not suitable for WSN since WSN networks are resource (e.g., memory, computation, and energy) limited. Key pre-distribution algorithms have recently evolved as efficient alternatives to key management in these networks. Secure communication is achieved between a pair of nodes either by a key allowing direct communication or a chain of keys. This paper considers prior knowledge of network characteristics and application constraints in terms of communication needs between sensor nodes. We propose methods to design key pre-distribution schemes to provide better security and connectivity while requiring fewer resources. Our methods are based on casting prior information as a graph. Motivated by this idea, we also propose a class of quasi-symmetric designs named g-designs. Our proposed key pre-distribution schemes significantly improve upon the existing constructions based on the unital designs. We give some examples and point out open problems for future research.
Keywords:
Balanced incomplete block design
Graph
Key pre-distribution
Quasi-symmetric design
Sensor networks
Perturbation Analysis of Orthogonal Matching Pursuit
Abstract:
Orthogonal Matching Pursuit (OMP) is a canonical greedy pursuit algorithm for sparse approximation. Previous studies of OMP have considered the recovery of a sparse signal through Φ and y = Φx + b, where is a matrix with more columns than rows and denotes the measurement noise. In this paper, based on Restricted Isometry Property, the performance of OMP is analyzed under general perturbations, which means both y and Φ are perturbed. Though the exact recovery of an almost sparse signal x is no longer feasible, the main contribution reveals that the support set of the best k-term approximation of x can be recovered under reasonable conditions. The error bound between x and the estimation of OMP is also derived. By constructing an example it is also demonstrated that the sufficient conditions for support recovery of the best k-term approximation of are rather tight. When x is strong-decaying, it is proved that the sufficient conditions for support recovery of the best k-term approximation of x can be relaxed, and the support can even be recovered in the order of the entries’ magnitude. Our results are also compared in detail with some related previous ones.
Keywords:
Compressed sensing
Orthogonal matching pursuit
Restricted isometry property
Strong-decaying signals