Data-Mining

Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable Algorithms and Performance Guarantees

  • Yongchun Li
  • Weijun Xie
    • Categories Data-Mining

    This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix with a given size out of a covariance matrix from a system. MESP has been widely applied to many areas, including healthcare, power system, manufacturing, data science, etc. Investigating its Lagrangian dual and primal characterization, we … Read more

    The perturbation analysis of nonconvex low-rank matrix robust recovery

  • Jianwen Huang
  • Wang Wendong
  • Feng Zhang
    • Categories Applications - Science and Engineering, Data-Mining

    In this paper, we bring forward a completely perturbed nonconvex Schatten $p$-minimization to address a model of completely perturbed low-rank matrix recovery. The paper that based on the restricted isometry property generalizes the investigation to a complete perturbation model thinking over not only noise but also perturbation, gives the restricted isometry property condition that guarantees … Read more

    Online matrix factorization for Markovian data and applications to Network Dictionary Learning

  • Laura Balzano
  • Hanbaek Lyu
  • Deanna Needell
    • Categories Data-Mining, Nonlinear Optimization Tags , , , ,

    Online Matrix Factorization (OMF) is a fundamental tool for dictionary learning problems, giving an approximate representation of complex data sets in terms of a reduced number of extracted features. Convergence guarantees for most of the OMF algorithms in the literature assume independence between data matrices, and the case of a dependent data stream remains largely … Read more

    On the Cluster-aware Supervised Learning (CluSL): Frameworks, Convergent Algorithms, and Applications

  • Shutong Chen
  • Weijun Xie
    • Categories Data-Mining Tags , , , , ,

    This paper proposes a cluster-aware supervised learning (CluSL) framework, which integrates the clustering analysis with supervised learning (SL). The objective of CluSL is to simultaneously find the best clusters of the data points and minimize the sum of loss functions within each cluster. This framework has many potential applications in healthcare, operations management, manufacturing, and … Read more

    A sparse semismooth Newton based augmented Lagrangian method for large-scale support vector machines

  • Dunbiao Niu
  • Enbin Song
  • Peipei Tang
  • Qingsong Wang
  • Chengjing Wang
    • Categories Convex and Nonsmooth Optimization, Data-Mining Tags , ,

    Support vector machines (SVMs) are successful modeling and prediction tools with a variety of applications. Previous work has demonstrated the superiority of the SVMs in dealing with the high dimensional, low sample size problems. However, the numerical difficulties of the SVMs will become severe with the increase of the sample size. Although there exist many … Read more

    Distance geometry and data science

  • Leo Liberti
    • Categories Data-Mining, Global Optimization Applications, Graphs and Matroids Tags , , , , ,

    Data are often represented as graphs. Many common tasks in data science are based on distances between entities. While some data science methodologies natively take graphs as their input, there are many more that take their input in vectorial form. In this survey we discuss the fundamental problem of mapping graphs to vectors, and its … Read more

    Optimal K-Thresholding Algorithms for Sparse Optimization Problems

  • Yun-Bin Zhao
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Data-Mining Tags , , , , ,

    The simulations indicate that the existing hard thresholding technique independent of the residual function may cause a dramatic increase or numerical oscillation of the residual. This inherit drawback of the hard thresholding renders the traditional thresholding algorithms unstable and thus generally inefficient for solving practical sparse optimization problems. How to overcome this weakness and develop … Read more

    An analysis of noise folding for low-rank matrix recovery

  • Wang Hailin
  • Jianjun Wang
  • Jianwen Huang
  • Wang Wendong
  • Feng Zhang
    • Categories Approximation Algorithms, Convex Optimization, Data-Mining

    Previous work regarding low-rank matrix recovery has concentrated on the scenarios in which the matrix is noise-free and the measurements are corrupted by noise. However, in practical application, the matrix itself is usually perturbed by random noise preceding to measurement. This paper concisely investigates this scenario and evidences that, for most measurement schemes utilized in … Read more

    High-Order Evaluation Complexity for Convexly-Constrained Optimization with Non-Lipschitzian Group Sparsity Terms

  • Xiaojun Chen
  • Philippe L. Toint
    • Categories Constrained Nonlinear Optimization, Data-Mining, Statistics Tags , , , , ,

    This paper studies high-order evaluation complexity for partially separable convexly-constrained optimization involving non-Lipschitzian group sparsity terms in a nonconvex objective function. We propose a partially separable adaptive regularization algorithm using a $p$-th order Taylor model and show that the algorithm can produce an (epsilon,delta)-approximate q-th-order stationary point in at most O(epsilon^{-(p+1)/(p-q+1)}) evaluations of the objective … Read more

    Approximating L1-Norm Best-Fit Lines

  • J. Paul Brooks
  • JH Dulá
    • Categories Data-Mining

    Sufficient conditions are provided for a deterministic algorithm for estimating an L1-norm best-fit one-dimensional subspace. To prove the conditions are sufficient, fundamental properties of the L1-norm projection of a point onto a one-dimensional subspace are derived. Also, an equivalence is established between the algorithm, which involves the calculation of several weighted medians, and independently-derived algorithms … Read more