Curse of dimensionality

The curse of dimensionality refers to various phenomena that arise when analyzing and organizing data in high-dimensional spaces that do not occur in low-dimensional settings such as the three-dimensional physical space of everyday experience. The expression was coined by Richard E. Bellman when considering problems in dynamic programming. Dimensionally cursed phenomena occur in domains such as numerical analysis, sampling, combinatorics, machine learning, data mining and databases. The common theme of these problems is that when the dimensionality increases, the volume of the space increases so fast that the available data become sparse. In order to obtain a reliable result, the amount of data needed often grows exponentially with the dimensionality. Also, organizing and searching data often relies on detecting areas where objects form groups with similar properties; in high dimensional data, however, all objects appear to be sparse and dissimilar in many ways, which prevents commo

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Related people

Related units

Related concepts

Related courses

Related lectures

Summary

Official source

About this result

Related publications (100)

Related publications

Related people (11)

Related people

Related units (10)

Related units

Related concepts (20)

Related concepts

Related courses (39)

Related courses

Related lectures (72)

Related lectures

Uncertainty-aware Model Inversion Networks

Romain Essy Théo Gratier De Saint-Louis

In this thesis, we assess a new framework called UMIN on a data-driven optimization problem. Such a problem happens recurrently in real life and can quickly become dicult to model when the input has a high dimensionality as images for instance. From the architecture of aircraft to the design of proteins, a great number of dierent techniques have already been explored. Based on former solutions, this work introduces a brand new Bayesian approach that updates previous frameworks. Former model architectures use generative adversarial networks on one side and a forward model on the other side to improve the accuracy of the results. However, employing a Bayesian network allows us to leverage its uncertainty estimates to enhance the accuracy of the results and also to reduce unrealistic samples output by the generator. By creating new experiments on a modern MNIST dataset and by reproducing former works taken as baseline, we show that the framework introduces in this work outperforms the previous method. The whole code is available at the following url: https://github.com/RomainGratier/Black-box_Optimization_via_Deep_ Generative-Exploratory_Networks.

2020

3D Reconstruction of Optical Diffraction Tomography Based on a Neural Network Model

Morteza Hasani Shoreh

Optical tomography has been widely investigated for biomedical imaging applications. In recent years, it has been combined with digital holography and has been employed to produce high quality images of phase objects such as cells. In this Thesis, we look into some of the newest optical Diffraction Tomography (DT) based techniques to solve Three-Dimensional (3D) reconstruction problems and discuss and compare some of the leading ideas and papers. Then we propose a neural-network-based algorithm to solve this problem and apply it on both synthetic and biological samples. Conventional phase tomography with coherent light and off axis recording is performed. The Beam Propagation Method (BPM) is used to model scattering and each x-y plane is modeled by a layer of neurons in the BPM. The network's output (simulated data) is compared to the experimental measurements and the error is used for correcting the weights of the neurons (the refractive indices of the nodes) using standard error back-propagation techniques. The proposed algorithm is detailed and investigated. Then, we look into resolution-conserving regularization and discuss a method for selecting regularizing parameters. In addition, the local minima and phase unwrapping problems are discussed and ways of avoiding them are investigated. It is shown that the proposed learning tomography (LT) achieves better performance than other techniques such as, DT especially when insufficient number or incomplete set of measurements is available. We also explore the role of regularization in obtaining higher fidelity images without losing resolution. It is experimentally shown that due to overcoming multiple scattering, the LT reconstruction greatly outperforms the DT when the sample contains two or more layers of cells or beads. Then, reconstruction using intensity measurements is investigated. 3D reconstruction of a live cell during apoptosis is presented in a time-lapse format. At the end, we present a final comparison with leading papers and commercially available systems. It is shown that -compared to other existing algorithms- the results of the proposed method have better quality. In particular, parasitic granular structures and the missing cone artifact are improved. Overall, the perspectives of our approach are pretty rich for high-resolution tomographic imaging in a range of practical applications.

EPFL2018

High-dimensional optimization under nonconvex excluded volume constraints

Antonio Sclocchi

We consider high-dimensional random optimization problems where the dynamical variables are subjected to nonconvex excluded volume constraints. We focus on the case in which the cost function is a simple quadratic cost and the excluded volume constraints are modeled by a perceptron constraint satisfaction problem. We show that depending on the density of constraints, one can have different situations. If the number of constraints is small, one typically has a phase where the ground state of the cost function is unique and sits on the boundary of the island of configurations allowed by the constraints. In this case, there is a hypostatic number of marginally satisfied constraints. If the number of constraints is increased one enters a glassy phase where the cost function has many local minima sitting again on the boundary of the regions of allowed configurations. At the phase transition point, the total number of marginally satisfied constraints becomes equal to the number of degrees of freedom in the problem and therefore we say that these minima are isostatic. We conjecture that by increasing further the constraints the system stays isostatic up to the point where the volume of available phase space shrinks to zero. We derive our results using the replica method and we also analyze a dynamical algorithm, the Karush-Kuhn-Tucker algorithm, through dynamical mean-field theory and we show how to recover the results of the replica approach in the replica symmetric phase.

AMER PHYSICAL SOC2022

Dimensionality reduction

Dimensionality reduction, or dimension reduction, is the transformation of data from a high-dimensional space into a low-dimensional space so that the low-dimensional representation retains some meani

Cluster analysis

Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense) to each other than to those in

K-nearest neighbors algorithm

In statistics, the k-nearest neighbors algorithm (k-NN) is a non-parametric supervised learning method first developed by Evelyn Fix and Joseph Hodges in 1951, and later expanded by Thomas Cover.

PHYS-467: Machine learning for physicists

Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practised.

EE-311: Fundamentals of machine learning

Ce cours présente une vue générale des techniques d'apprentissage automatique, passant en revue les algorithmes, le formalisme théorique et les protocoles expérimentaux.

CS-401: Applied data analysis

This course teaches the basic techniques, methodologies, and practical skills required to draw meaningful insights from a variety of data, with the help of the most acclaimed software tools in the data science world (pandas, scikit-learn, Spark, etc.)