Data-Mining

Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Sean Lo
  • Jean Pauphilet
    • Categories Data-Mining, Global Optimization Theory, Semi-definite Programming

    Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible, and has numerous applications such as product recommendation. Unfortunately, existing methods for solving low-rank matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not possess any optimality guarantees. … Read more

    Bilevel optimization with a multi-objective lower-level problem: Risk-neutral and risk-averse formulations

  • Tommaso Giovannelli
  • Griffin D. Kent
  • Luis Nunes Vicente
    • Categories Data-Mining, Multi-Criteria Optimization, Stochastic Programming Tags , , ,

    In this work, we propose different formulations and gradient-based algorithms for deterministic and stochastic bilevel problems with conflicting objectives in the lower level. Such problems have received little attention in the deterministic case and have never been studied from a stochastic approximation viewpoint despite the recent advances in stochastic methods for single-level, bilevel, and multi-objective … Read more

    Sparse PCA With Multiple Components

  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories Data Science Theory, Data-Mining, Semi-definite Programming

    Sparse Principal Component Analysis is a cardinal technique for obtaining combinations of features, or principal components (PCs), that explain the variance of high-dimensional datasets in an interpretable manner. At its heart, this involves solving a sparsity and orthogonality constrained convex maximization problem, which is extremely computationally challenging. Most existing work address sparse PCA via heuristics … Read more

    A new sufficient condition for non-convex sparse recovery via weighted $\ell_r\!-\!\ell_1$ minimization

  • Jianwen Huang
  • Feng Zhang
    • Categories Data-Mining, Nonsmooth Optimization Tags , , ,

    In this letter, we discuss the reconstruction of sparse signals from undersampled data, which belongs to the core content of compressed sensing. A new sufficient condition in terms of the restricted isometry constant (RIC) and restricted orthogonality constant (ROC) is first established for the performance guarantee of recently proposed non-convex weighted $\ell_r-\ell_1$ minimization in recovering … Read more

    The Null Space Property of the Weighted $\ell_r-\ell_1$ Minimization

  • Jianwen Huang
  • Xinling Liu
    • Categories Data-Mining, Nonsmooth Optimization, Robust Optimization Tags , , ,

    The null space property (NSP), which relies merely on the null space of the sensing matrix column space, has drawn numerous interests in sparse signal recovery. This article studies NSP of the weighted $\ell_r-\ell_1$ minimization. Several versions of NSP of the weighted $\ell_r-\ell_1$ minimization including the weighted $\ell_r-\ell_1$ NSP, the weighted $\ell_r-\ell_1$ stable NSP, the … Read more

    The Combinatorial Brain Surgeon: Pruning Weights That Cancel One Another in Neural Networks

  • Xin Yu
  • Thiago Serra
  • Shandian Zhe
  • Srikumar Ramalingam
    • Categories Data-Mining, Meta Heuristics, Quadratic Programming Tags , ,

    Neural networks tend to achieve better accuracy with training if they are larger — even if the resulting models are overparameterized. Nevertheless, carefully removing such excess parameters before, during, or after training may also produce models with similar or even improved accuracy. In many cases, that can be curiously achieved by heuristics as simple as … Read more

    Mixed-Integer Programming Techniques for the Minimum Sum-of-Squares Clustering Problem

  • Jan Pablo Burgard
  • Carina Moreira Costa
  • Christopher Hojny
  • Kleinert Thomas
  • Martin Schmidt
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Data-Mining Tags , , ,

    The minimum sum-of-squares clustering problem is a very important problem in data mining and machine learning with very many applications in, e.g., medicine or social sciences. However, it is known to be NP-hard in all relevant cases and to be notoriously hard to be solved to global optimality in practice. In this paper, we develop … Read more

    Stable Recovery of Sparse Signals With Non-convex Weighted $r$-Norm Minus $1$-Norm

  • Jianwen Huang
  • Feng Zhang
  • Xinling Liu
  • Jianjun Wang
    • Categories Constrained Nonlinear Optimization, Data-Mining, Nonsmooth Optimization Tags , , ,

    Given the measurement matrix $A$ and the observation signal $y$, the central purpose of compressed sensing is to find the most sparse solution of the underdetermined linear system $y=Ax+z$, where $x$ is the $s$-sparse signal to be recovered and $z$ is the noise vector. Zhou and Yu \cite{Zhou and Yu 2019} recently proposed a novel … Read more

    Time-series aggregation for the optimization of energy systems: goals, challenges, approaches, and opportunities

  • Holger Teichgraeber
  • Adam R. Brandt
    • Categories Data-Mining, Energy, Facility Planning and Design Tags , , , , ,

    The rising significance of renewable energy increases the importance of representing time-varying input data in energy system optimization studies. Time-series aggregation, which reduces temporal model complexity, has emerged in recent years to address this challenge. We provide a comprehensive review of time-series aggregation for the optimization of energy systems. We show where time series affect … Read more