Back to search

Technical University of Crete (TUC)

On clustering, classification and dictionary learning: a theoretical revisit of robust kmeans, nearest-neighbour classification and dictionary learning with Moreau envelopes

Abstract

dc:description

The problem of risk minimization on the basis of empirical data is rather general and includes as particular cases three basic statistical problems: i) the problem of classification, ii) the problem of clustering, and iii) the problem of dictionary learning. Classification and clustering have a long history while dictionary learning is a recent branch of machine learning that aims at finding a matrix, or else dictionary, which provides sparse representations for the data points of a problem. This thesis consists of three parts and is specifically concerned with statistical properties of algorithms that solve these three fundamental data analysis problems.The first part presents new results regarding a popular variant of the k-means clustering procedure, robust k-means. While, in many cases, ordinary Euclidean k-means yields informative cluster structures, there exist cases where its performance dramatically deteriorates in the presence of arbitrary perturbations of input data. Robust k-means tries to resolve known robustness weaknesses of ordinary Euclidean k-means using a bounded loss function. In the second part, we study the asymptotic properties of special nearest-neighbor classification rules. These rules use variants of the k-means clustering procedure to generate a set of properly labeled vectors in which the nearest neighbor rule will search for neighbors of a query point. The third part concerns a variant of the dictionary learning problem with a special type of reconstruction loss which replaces the ordinary Euclidean squared loss. In this part, we derive generalization bounds for the dictionary learning problem when the empirical loss function is a Moreau envelope, a well studied function transformation with origins in variational analysis. A new sample complexity result, concerning the case of k-sparse representation vectors, removes a redundant condition regarding the coherence of dictionaries appearing in previous works.

Degree

thesis:*
Grantor dc:publisher
Technical University of Crete (TUC)
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Georgogiannis, Alexandros
  • Γεωργογιάννης, Αλέξανδρος

Subjects

dc:subject × 22

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/52159

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Georgogiannis, Alexandros; Γεωργογιάννης, Αλέξανδρος. On clustering, classification and dictionary learning: a theoretical revisit of robust kmeans, nearest-neighbour classification and dictionary learning with Moreau envelopes. Technical University of Crete (TUC), 2022. http://hdl.handle.net/10442/hedi/52159