Compressed Regression

Recent research has studied the role of sparsity in high dimensional regression and signal reconstruction, establishing theoretical limits for recovering sparse models from sparse data. In this paper we study a variant of this problem where the original n input variables are compressed by a random linear transformation to m ≪ n examples in p dimensions, and establish conditions under which a sparse linear model can be successfully recovered from the compressed data. A primary motivation for this compression procedure is to anonymize the data and preserve privacy by revealing little information about the original data. We characterize the number of random projections that are required for l1-regularized compressed regression to identify the nonzero coefficients in the true model with probability approaching one, a property called "sparsistence." In addition, we show that l1-regularized compressed regression asymptotically predicts as well as an oracle linear model, a property called "persistence." Finally, we characterize the privacy properties of the compression procedure in information-theoretic terms, establishing upper bounds on the rate of information communicated between the compressed and uncompressed data that decay to zero.

• Publication year

  2007

• Venue

  Neural Information Processing Systems

• Publication date

  2007-06-04

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 0706.0534
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• 双対平坦空間におけるLeast Angle Regressionと情報量規準

  2009cited by this paper
• LASSO-TYPE RECOVERY OF SPARSE REPRESENTATIONS FOR HIGH-DIMENSIONAL DATA

  2008cited by this paper
• Random orthogonal matrix masking methodology for microdata release

  2008cited by this paper
• High-Dimensional Graphical Model Selection Using $\ell_1$-Regularized Logistic Regression

  2008cited by this paper
• The price of privacy and the limits of LP decoding

  2007cited by this paper
• The smashed filter for compressive classification and target recognition

  2007cited by this paper
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting

  2007cited by this paper
• Compressed Sensing and Redundant Dictionaries

  2007cited by this paper
• On Model Selection Consistency of Lasso

  2006cited by this paper
• Differential Privacy

  2006cited by this paper
• Sharp thresholds for high-dimensional and noisy recovery of sparsity

  2006influential reference
• Sparse Signal Detection from Incoherent Projections

  2006cited by this paper
• Thresholds for the Recovery of Sparse Solutions via L1 Minimization

  2006cited by this paper
• Random projection-based multiplicative data perturbation for privacy preserving distributed data mining

  2006cited by this paper
• High-dimensional graphs and variable selection with the Lasso

  2006cited by this paper
• Compressive Sampling for Signal Classification

  2006cited by this paper
• Stable recovery of sparse overcomplete representations in the presence of noise

  2006cited by this paper
• Detection and estimation with compressive measurements

  2006cited by this paper
• Polylogarithmic Private Approximations and Efficient Matching

  2006cited by this paper
• Stable signal recovery from incomplete and inaccurate measurements

  2005cited by this paper
• Persistence in high-dimensional linear predictor selection and the virtue of overparametrization

  2004cited by this paper
• Greed is good: algorithmic results for sparse approximation

  2004cited by this paper
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

  2004cited by this paper
• Privacy preserving regression modelling via distributed computation

  2004cited by this paper
• Secure multiparty computation of approximations

  2001cited by this paper
• On the capacity of multi-antenna Gaussian channels

  2001cited by this paper
• On the design and quantification of privacy preserving data mining algorithms

  2001cited by this paper
• Chi-square oracle inequalities

  2000cited by this paper
• On the LASSO and its Dual

  2000cited by this paper
• Capacity of a Mobile Multiple-Antenna Communication Link in Rayleigh Flat Fading

  1999cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Enhancing Access to Microdata while Protecting Confidentiality: Prospects for the Future

  1991cited by this paper
• Probability in Banach Spaces: Isoperimetry and Processes

  1991cited by this paper
• Matrix analysis

  1985cited by this paper
• Extensions of Lipschitz mappings into Hilbert space

  1984cited by this paper
• Privacy transformations for statistical information systems

  1977cited by this paper
• Probability Inequalities for the Sum of Independent Random Variables

  1962cited by this paper

• Bayesian Data Sketching for Varying Coefficient Regression Models

  2025cites this paper
• Distributed Hybrid Sketching for ℓ2-Embeddings

  2024cites this paper
• Distributed Local Sketching for £2 Embeddings

  2024cites this paper
• Robust Distributed Learning of Functional Data From Simulators through Data Sketching

  2024cites this paper
• Sparse data-driven random projection in regression for high-dimensional data

  2023cites this paper
• Iterative Sketching for Secure Coded Regression

  2023cites this paper
• Bayesian Data Sketching for Spatial Regression Models

  2022cites this paper
• Orthonormal Sketches for Secure Coded Regression

  2022cites this paper
• Linear Discriminant Analysis with the Randomized Kaczmarz Method

  2022cites this paper
• Sketching in High-Dimensional Regression With Big Data Using Gaussian Scale Mixture Priors

  2022influential citation
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration, and Lower Bounds

  2022cites this paper
• Information-Theoretic Bounds on Sketching

  2021cites this paper
• Sketching in Bayesian High Dimensional Regression With Big Data Using Gaussian Scale Mixture Priors

  2021influential citation
• An Introduction to Johnson-Lindenstrauss Transforms

  2021cites this paper
• Distributed Sketching Methods for Privacy Preserving Regression

  2020cites this paper
• High-dimensional model recovery from random sketched data by exploring intrinsic sparsity

  2020influential citation
• Bayesian Pseudocoresets

  2020influential citation
• Privacy Preserving Efficient Computation in Bayesian High Dimensional Regression With Big Data Using Gaussian Scale Mixture Priors

  2020cites this paper
• Compressing large sample data for discriminant analysis

  2020cites this paper
• A projector-based approach to quantifying total and excess uncertainties for sketched linear regression

  2018cites this paper
• Information-Theoretic Methods in Data Science Information-theoretic bounds on sketching

  2018cites this paper
• Analysis of the most recent modelling techniques for big data with particular attention to Bayesian ones

  2018cites this paper
• A New Theory for Sketching in Linear Regression

  2018cites this paper
• Private Incremental Regression

  2017cites this paper
• Random Projections for Large-Scale Regression

  2017influential citation
• Differentially Private Ordinary Least Squares

  2015cites this paper
• Estimates on compressed neural networks regression

  2015cites this paper
• Differentially Private Least Squares: Estimation, Confidence and Rejecting the Null Hypothesis

  2015cites this paper
• Fast Sparse Least-Squares Regression with Non-Asymptotic Guarantees

  2015cites this paper
• Compressed Predictive State Representation: An Efficient Moment-Method for Sequence Prediction and Sequential Decision-Making

  2014cites this paper
• Compressed classification learning with Markov chain samples

  2014cites this paper
• Scalable Nonparametric Bayes Learning

  2013cites this paper
• Efficient learning and planning with compressed predictive states

  2013cites this paper
• Learning with Limited Supervision by Input and Output Coding

  2012cites this paper
• Learning Parameters of Linear Models in Compressed Parameter Space

  2012cites this paper
• Compressed Least-Squares Regression on Sparse Spaces

  2012cites this paper
• Bellman Error Based Feature Generation using Random Projections on Sparse Spaces

  2012cites this paper
• Privacy Aware Learning

  2012cites this paper
• A Novel Direction Finding Method Based on Compressed Least-Squared Regression

  2011cites this paper
• Least-Squares Regression on Sparse Spaces

  2011cites this paper
• Exploiting Auxiliary Information in the Estimation of Per-Record Risk of Disclosure

  2010cites this paper
• Compressed Learning with Regular Concept

  2010cites this paper
• High-dimensional Variable Selection with Sparse Random Projections: Measurement Sparsity and Statistical Efficiency

  2010cites this paper
• Learning Compressible Models

  2010cites this paper
• On the Asymptotic Properties of The Group Lasso Estimator in Least Squares Problems

  2009cites this paper
• Compressed Least-Squares Regression

  2009cites this paper
• Limitation : an Overview of Issues and Methodological Solutions

  2008cites this paper
• On the asymptotic properties of the group lasso estimator for linear models

  2008influential citation
• On the ℓ 1 -ℓ q Regularized Regression

  2008cites this paper
• Bayesian Data Sketching for Varying Coe ffi cient Regression Models

  year unknowncites this paper