Convex Relaxation for Low-Dimensional Representation: Phase Transitions and Limitations

There is a growing interest in taking advantage of possible patterns and structures in data so as to extract the desired information and overcome the curse of dimensionality. In a wide range of applications, including computer vision, machine learning, medical imaging, and social networks, the signal that gives rise to the observations can be modeled to be approximately sparse and exploiting this fact can be very beneficial. This has led to an immense interest in the problem of efficiently reconstructing a sparse signal from limited linear observations. More recently, low-rank approximation techniques have become prominent tools to approach problems arising in machine learning, system identification and quantum tomography.

In sparse and low-rank estimation problems, the challenge is the inherent intractability of the objective function, and one needs efficient methods to capture the low-dimensionality of these models. Convex optimization is often a promising tool to attack such problems. An intractable problem with a combinatorial objective can often be "relaxed" to obtain a tractable but almost as powerful convex optimization problem. This dissertation studies convex optimization techniques that can take advantage of low-dimensional representations of the underlying high-dimensional data. We provide provable guarantees that ensure that the proposed algorithms will succeed under reasonable conditions, and answer questions of the following flavor:

More specifically, i) Focusing on linear inverse problems, we generalize the classical error bounds known for the least-squares technique to the lasso formulation, which incorporates the signal model. ii) We show that intuitive convex approaches do not perform as well as expected when it comes to signals that have multiple low-dimensional structures simultaneously. iii) Finally, we propose convex relaxations for the graph clustering problem and give sharp performance guarantees for a family of graphs arising from the so-called stochastic block model. We pay particular attention to the following aspects. For i) and ii), we aim to provide a general geometric framework, in which the results on sparse and low-rank estimation can be obtained as special cases. For i) and iii), we investigate the precise performance characterization, which yields the right constants in our bounds and the true dependence between the problem parameters.

A three-dimensional representation method for noisy point clouds based on growing self-organizing maps accelerated on GPUs

The research described in this thesis was motivated by the need of a robust model capable of representing 3D data obtained with 3D sensors, which are inherently noisy. In addition, time constraints have to be considered as these sensors are capable of providing a 3D data stream in real time. This thesis proposed the use of Self-Organizing Maps (SOMs) as a 3D representation model. In particular, we proposed the use of the Growing Neural Gas (GNG) network, which has been successfully used for clustering, pattern recognition and topology representation of multi-dimensional data. Until now, Self-Organizing Maps have been primarily computed offline and their application in 3D data has mainly focused on free noise models, without considering time constraints. It is proposed a hardware implementation leveraging the computing power of modern GPUs, which takes advantage of a new paradigm coined as General-Purpose Computing on Graphics Processing Units (GPGPU). The proposed methods were applied to different problem and applications in the area of computer vision such as the recognition and localization of objects, visual surveillance or 3D reconstruction.

Creative Commons licences and design Are the two compatible?

This article analyses whether Creative Commons licences are applicable to and compatible with design. The first part focuses on the peculiar and complex nature of a design, which can benefit from a copyright and a design protection. This shows how it can affect the use of Creative Commons licences. The second and third parts deal with a specific case study. Some Internet platforms have recently emerged that offer users the possibility to download blueprints of design products in order to build them. Designers and creative users are invited to share their blueprints and creations under Creative Commons licences. The second part of the article assesses whether digital blueprints can be copyrightable and serve as the subject matter of Creative Commons licences, while the last part assesses whether the right to reproduce the digital blueprint, as provided by Creative Commons licences, extends to the right to build the product.

Cognitive load and assembly tasks : effect of instructional formats on learning assembly procedures

The study investigated the effect on learning of four different instructional formats used to teach assembly procedures. Cognitive load and spatial information processing theories were used to generate the instructional material. The first group received a physical model to study, the second an isometric drawing, the third an isometric drawing plus a model and the fourth an orthographic drawing. Forty secondary school students were presented with the four different instructional formats and subsequently tested on an assembly task. The findings indicated that there may be evidence to argue that the model format which only required encoding of an already constructed three dimensional representation, caused less extraneous cognitive load compared to the isometric and the orthographic formats. No significant difference was found between the model and the isometric-plus-model formats on all measures because 80% of the students in the isometric-plus-model format chose to use the model format only. The model format also did not differ significantly from other groups in total time taken to complete the assembly, in number of correctly assembled pieces and in time spent on studying the tasks. However, the model group had significantly more correctly completed models and required fewer extra looks than the other groups.

Evaluation of texture and geometry for dimensional facial expression recognition

Facial expression recognition (FER) algorithms mainly focus on classification into a small discrete set of emotions or representation of emotions using facial action units (AUs). Dimensional representation of emotions as continuous values in an arousal-valence space is relatively less investigated. It is not fully known whether fusion of geometric and texture features will result in better dimensional representation of spontaneous emotions. Moreover, the performance of many previously proposed approaches to dimensional representation has not been evaluated thoroughly on publicly available databases. To address these limitations, this paper presents an evaluation framework for dimensional representation of spontaneous facial expressions using texture and geometric features. SIFT, Gabor and LBP features are extracted around facial fiducial points and fused with FAP distance features. The CFS algorithm is adopted for discriminative texture feature selection. Experimental results evaluated on the publicly accessible NVIE database demonstrate that fusion of texture and geometry does not lead to a much better performance than using texture alone, but does result in a significant performance improvement over geometry alone. LBP features perform the best when fused with geometric features. Distributions of arousal and valence for different emotions obtained via the feature extraction process are compared with those obtained from subjective ground truth values assigned by viewers. Predicted valence is found to have a more similar distribution to ground truth than arousal in terms of covariance or Bhattacharya distance, but it shows a greater distance between the means.

On the Geometry of Infinite-Dimensional Grassmannian Manifolds and Gauge Theory

This PhD Thesis is about certain infinite-dimensional Grassmannian manifolds that arise naturally in geometry, representation theory and mathematical physics. From the physics point of view one encounters these infinite-dimensional manifolds when trying to understand the second quantization of fermions. The many particle Hilbert space of the second quantized fermions is called the fermionic Fock space. A typical element of the fermionic Fock space can be thought to be a linear combination of the configurations m particles and n anti-particles . Geometrically the fermionic Fock space can be constructed as holomorphic sections of a certain (dual)determinant line bundle lying over the so called restricted Grassmannian manifold, which is a typical example of an infinite-dimensional Grassmannian manifold one encounters in QFT. The construction should be compared with its well-known finite-dimensional analogue, where one realizes an exterior power of a finite-dimensional vector space as the space of holomorphic sections of a determinant line bundle lying over a finite-dimensional Grassmannian manifold. The connection with infinite-dimensional representation theory stems from the fact that the restricted Grassmannian manifold is an infinite-dimensional homogeneous (Kähler) manifold, i.e. it is of the form G/H where G is a certain infinite-dimensional Lie group and H its subgroup. A central extension of G acts on the total space of the dual determinant line bundle and also on the space its holomorphic sections; thus G admits a (projective) representation on the fermionic Fock space. This construction also induces the so called basic representation for loop groups (of compact groups), which in turn are vitally important in string theory / conformal field theory. The Thesis consists of three chapters: the first chapter is an introduction to the backround material and the other two chapters are individually written research articles. The first article deals in a new way with the well-known question in Yang-Mills theory, when can one lift the action of the gauge transformation group on the space of connection one forms to the total space of the Fock bundle in a compatible way with the second quantized Dirac operator. In general there is an obstruction to this (called the Mickelsson-Faddeev anomaly) and various geometric interpretations for this anomaly, using such things as group extensions and bundle gerbes, have been given earlier. In this work we give a new geometric interpretation for the Faddeev-Mickelsson anomaly in terms of differentiable gerbes (certain sheaves of categories) and central extensions of Lie groupoids. The second research article deals with the question how to define a Dirac-like operator on the restricted Grassmannian manifold, which is an infinite-dimensional space and hence not in the landscape of standard Dirac operator theory. The construction relies heavily on infinite-dimensional representation theory and one of the most technically demanding challenges is to be able to introduce proper normal orderings for certain infinite sums of operators in such a way that all divergences will disappear and the infinite sum will make sense as a well-defined operator acting on a suitable Hilbert space of spinors. This research article was motivated by a more extensive ongoing project to construct twisted K-theory classes in Yang-Mills theory via a Dirac-like operator on the restricted Grassmannian manifold.

Scalable multi-dimensional user intent identification using tree structured distributions

The problem of identifying user intent has received considerable attention in recent years, particularly in the context of improving the search experience via query contextualization. Intent can be characterized by multiple dimensions, which are often not observed from query words alone. Accurate identification of Intent from query words remains a challenging problem primarily because it is extremely difficult to discover these dimensions. The problem is often significantly compounded due to lack of representative training sample. We present a generic, extensible framework for learning the multi-dimensional representation of user intent from the query words. The approach models the latent relationships between facets using tree structured distribution which leads to an efficient and convergent algorithm, FastQ, for identifying the multi-faceted intent of users based on just the query words. We also incorporated WordNet to extend the system capabilities to queries which contain words that do not appear in the training data. Empirical results show that FastQ yields accurate identification of intent when compared to a gold standard.

The Representation of Emotion in Autonomic and Central Nervous System Activity

Phenomenologically, humans effectively label and report feeling distinct emotions, yet the extent to which emotions are represented categorically in nervous system activity is controversial. Theoretical accounts differ in this regard, some positing distinct emotional experiences emerge from a dimensional representation (e.g., along axes of valence and arousal) whereas others propose emotions are natural categories, with dedicated neural bases and associated response profiles. This dissertation aims to empirically assess these theoretical accounts by examining how emotions are represented (either as disjoint categories or as points along continuous dimensions) in autonomic and central nervous system activity by integrating psychophysiological recording and functional neuroimaging with machine-learning based analytical methods. Results demonstrate that experientially, emotional events are well-characterized both along dimensional and categorical frameworks. Measures of central and peripheral responding discriminate among emotion categories, but are largely independent of valence and arousal. These findings suggest dimensional and categorical aspects of emotional experience are driven by separable neural substrates and demonstrate that emotional states can be objectively quantified on the basis of nervous system activity.

Simplifying the representation of complex free-energy landscapes using sketch-map

A new scheme, sketch-map, for obtaining a low-dimensional representation of the region of phase space explored during an enhanced dynamics simulation is proposed. We show evidence, from an examination of the distribution of pairwise distances between frames, that some features of the free-energy surface are inherently high-dimensional. This makes dimensionality reduction problematic because the data does not satisfy the assumptions made in conventional manifold learning algorithms We therefore propose that when dimensionality reduction is performed on trajectory data one should think of the resultant embedding as a quickly sketched set of directions rather than a road map. In other words, the embedding tells one about the connectivity between states but does not provide the vectors that correspond to the slow degrees of freedom. This realization informs the development of sketch-map, which endeavors to reproduce the proximity information from the high-dimensionality description in a space of lower dimensionality even when a faithful embedding is not possible.

Finite-size scaling analysis of the avalanches in the three-dimensional Gaussian random-field Ising model with metastable dynamics

A numerical study is presented of the third-dimensional Gaussian random-field Ising model at T=0 driven by an external field. Standard synchronous relaxation dynamics is employed to obtain the magnetization versus field hysteresis loops. The focus is on the analysis of the number and size distribution of the magnetization avalanches. They are classified as being nonspanning, one-dimensional-spanning, two-dimensional-spanning, or three-dimensional-spanning depending on whether or not they span the whole lattice in different space directions. Moreover, finite-size scaling analysis enables identification of two different types of nonspanning avalanches (critical and noncritical) and two different types of three-dimensional-spanning avalanches (critical and subcritical), whose numbers increase with L as a power law with different exponents. We conclude by giving a scenario for avalanche behavior in the thermodynamic limit.

Monitoring and modelling the three-dimensional flow of water under drip irrigation

The interpretation of soil water dynamics under drip irrigation systems is relevant for crop production as well as on water use and management. In this study a three-dimensional representation of the flow of water under drip irrigation is presented. The work includes analysis of the water balance at point scale as well as area-average, exploring uncertainties in water balance estimations depending on the number of locations sampled. The water flow was monitored by detailed profile water content measurements before irrigation, after irrigation and 24 h later with a dense array of soil moisture access tubes radially distributed around selected drippers. The objective was to develop a methodology that could be used on selected occasions to obtain 'snap shots' of the detailed three-dimensional patterns of soil moisture. Such patterns are likely to be very complex, as spatial variability will be induced for a number of reasons, such as strong horizontal gradients in soil moisture, variations between individual sources in the amount of water applied and spatial variability is soil hydraulic properties. Results are compared with a widely used numerical model, Hydrus-2D. The observed dynamic of the water content distribution is in good agreement with model simulations, although some discrepancies concerning the horizontal distribution of the irrigation bulb are noted due to soil heterogeneity. (c) 2006 Elsevier B.V. All rights reserved.

Light microscopy and computer three-dimensional reconstruction of the blood capillaries of the enamel organ of rat molar tooth germs

We performed a light microscope and a computer three-dimensional reconstruction study of serial sections of the molar enamel organ of 3- and 5-day-old rats perfused with Indian ink through the arterial system. The tooth germs were fixed in Bouin's solution, embedded in paraffin, sectioned and stained with haematoxylin and eosin. For the three-dimensional reconstruction, light micrographs of the serial sections were digitized, and aligned using the serial EM Align software downloaded from http://synapses.bu.edu/tools/. After alignment, the boundaries of the India-ink-filled blood vessels were manually traced with a mouse using the software IGL trace (version 1.26b), also downloaded from the above website. After tracing, a three-dimensional representation of the blood vessel contours was generated in a VRML format and visualized with the help of the software Cortona Web3D viewer (version 4.0) downloaded from http://www.parallelgraphics.com/products/cortona. Our results showed that in regions where ameloblasts are polarized the capillaries are arranged in three distinct levels: (1) penetrating and leaving capillaries in relation to the outer enamel epithelium; (2) capillaries crossing and branching inside the stellate reticulum; and (3) capillaries branching and anastomosing profusely within the stratum intermedium, thereby forming an extensive capillary plexus intimately associated with the cells of the stratum intermedium. The existence of a conspicuous capillary plexus intermingled with cells of the stratum intermedium, as shown in our results, suggests that some molecules produced by cells of the stratum intermedium could be released into the capillary plexus and thereafter carried to the dental follicle.

Kernel Methods for Tree Structured Data

Machine learning comprises a series of techniques for automatic extraction of meaningful information from large collections of noisy data. In many real world applications, data is naturally represented in structured form. Since traditional methods in machine learning deal with vectorial information, they require an a priori form of preprocessing. Among all the learning techniques for dealing with structured data, kernel methods are recognized to have a strong theoretical background and to be effective approaches. They do not require an explicit vectorial representation of the data in terms of features, but rely on a measure of similarity between any pair of objects of a domain, the kernel function. Designing fast and good kernel functions is a challenging problem. In the case of tree structured data two issues become relevant: kernel for trees should not be sparse and should be fast to compute. The sparsity problem arises when, given a dataset and a kernel function, most structures of the dataset are completely dissimilar to one another. In those cases the classifier has too few information for making correct predictions on unseen data. In fact, it tends to produce a discriminating function behaving as the nearest neighbour rule. Sparsity is likely to arise for some standard tree kernel functions, such as the subtree and subset tree kernel, when they are applied to datasets with node labels belonging to a large domain. A second drawback of using tree kernels is the time complexity required both in learning and classification phases. Such a complexity can sometimes prevents the kernel application in scenarios involving large amount of data. This thesis proposes three contributions for resolving the above issues of kernel for trees. A first contribution aims at creating kernel functions which adapt to the statistical properties of the dataset, thus reducing its sparsity with respect to traditional tree kernel functions. Specifically, we propose to encode the input trees by an algorithm able to project the data onto a lower dimensional space with the property that similar structures are mapped similarly. By building kernel functions on the lower dimensional representation, we are able to perform inexact matchings between different inputs in the original space. A second contribution is the proposal of a novel kernel function based on the convolution kernel framework. Convolution kernel measures the similarity of two objects in terms of the similarities of their subparts. Most convolution kernels are based on counting the number of shared substructures, partially discarding information about their position in the original structure. The kernel function we propose is, instead, especially focused on this aspect. A third contribution is devoted at reducing the computational burden related to the calculation of a kernel function between a tree and a forest of trees, which is a typical operation in the classification phase and, for some algorithms, also in the learning phase. We propose a general methodology applicable to convolution kernels. Moreover, we show an instantiation of our technique when kernels such as the subtree and subset tree kernels are employed. In those cases, Direct Acyclic Graphs can be used to compactly represent shared substructures in different trees, thus reducing the computational burden and storage requirements.

Supervisión multidistribuida para el control de procesos de conservación de productos agroalimentarios: optimización de calidad del producto

La presente Tesis está orientada al análisis de la supervisión multidistribuida de tres procesos agroalimentarios: el secado solar, el transporte refrigerado y la fermentación de café, a través de la información obtenida de diferentes dispositivos de adquisición de datos, que incorporan sensores, así como el desarrollo de metodologías de análisis de series temporales, modelos y herramientas de control de procesos para la ayuda a la toma de decisiones en las operaciones de estos entornos. En esta tesis se han utilizado: tarjetas RFID (TemTrip®) con sistema de comunicación por radiofrecuencia y sensor de temperatura; el registrador (i-Button®), con sensor integrado de temperatura y humedad relativa y un tercer prototipo empresarial, módulo de comunicación inalámbrico Nlaza, que integra un sensor de temperatura y humedad relativa Sensirion®. Estos dispositivos se han empleado en la conformación de redes multidistribuidas de sensores para la supervisión de: A) Transportes de producto hortofrutícola realizados en condiciones comerciales reales, que son: dos transportes terrestre de producto de IV gama desde Murcia a Madrid; transporte multimodal (barco-barco) de limones desde Montevideo (Uruguay) a Cartagena (España) y transporte multimodal (barco-camión) desde Montevideo (Uruguay) a Verona (Italia). B) dos fermentaciones de café realizadas en Popayán (Colombia) en un beneficiadero. Estas redes han permitido registrar la dinámica espacio-temporal de temperaturas y humedad relativa de los procesos estudiados. En estos procesos de transporte refrigerado y fermentación la aplicación de herramientas de visualización de datos y análisis de conglomerados, han permitido identificar grupos de sensores que presentan patrones análogos de sus series temporales, caracterizando así zonas con dinámicas similares y significativamente diferentes del resto y permitiendo definir redes de sensores de menor densidad cubriendo las diferentes zonas identificadas. Las metodologías de análisis complejo de las series espacio-temporales (modelos psicrométricos, espacio de fases bidimensional e interpolaciones espaciales) permitieron la cuantificación de la variabilidad del proceso supervisado tanto desde el punto de vista dinámico como espacial así como la identificación de eventos. Constituyendo así herramientas adicionales de ayuda a la toma de decisiones en el control de los procesos. Siendo especialmente novedosa la aplicación de la representación bidimensional de los espacios de fases en el estudio de las series espacio-temporales de variables ambientales en aplicaciones agroalimentarias, aproximación que no se había realizado hasta el momento. En esta tesis también se ha querido mostrar el potencial de un sistema de control basado en el conocimiento experto como es el sistema de lógica difusa. Se han desarrollado en primer lugar, los modelos de estimación del contenido en humedad y las reglas semánticas que dirigen el proceso de control, el mejor modelo se ha seleccionado mediante un ensayo de secado realizado sobre bolas de hidrogel como modelo alimentario y finalmente el modelo se ha validado mediante un ensayo en el que se deshidrataban láminas de zanahoria. Los resultados sugirieron que el sistema de control desarrollado, es capaz de hacer frente a dificultades como las variaciones de temperatura día y noche, consiguiendo un producto con buenas características de calidad comparables a las conseguidas sin aplicar ningún control sobre la operación y disminuyendo así el consumo energético en un 98% con respecto al mismo proceso sin control. La instrumentación y las metodologías de análisis de datos implementadas en esta Tesis se han mostrado suficientemente versátiles y transversales para ser aplicadas a diversos procesos agroalimentarios en los que la temperatura y la humedad relativa sean criterios de control en dichos procesos, teniendo una aplicabilidad directa en el sector industrial ABSTRACT This thesis is focused on the analysis of multi-distributed supervision of three agri-food processes: solar drying, refrigerated transport and coffee fermentation, through the information obtained from different data acquisition devices with incorporated sensors, as well as the development of methodologies for analyzing temporary series, models and tools to control processes in order to help in the decision making in the operations within these environments. For this thesis the following has been used: RFID tags (TemTrip®) with a Radiofrequency ID communication system and a temperature sensor; the recorder (i-Button®), with an integrated temperature and relative humidity and a third corporate prototype, a wireless communication module Nlaza, which has an integrated temperature and relative humidity sensor, Sensirion®. These devices have been used in creating three multi-distributed networks of sensors for monitoring: A) Transport of fruits and vegetables made in real commercial conditions, which are: two land trips of IV range products from Murcia to Madrid; multimodal transport (ship - ship) of lemons from Montevideo (Uruguay) to Cartagena (Spain) and multimodal transport (ship - truck) from Montevideo (Uruguay) to Verona (Italy). B) Two coffee fermentations made in Popayan (Colombia) in a coffee processing plant. These networks have allowed recording the time space dynamics of temperatures and relative humidity of the processed under study. Within these refrigerated transport and fermentation processes, the application of data display and cluster analysis tools have allowed identifying sensor groups showing analogical patterns of their temporary series; thus, featuring areas with similar and significantly different dynamics from the others and enabling the definition of lower density sensor networks covering the different identified areas. The complex analysis methodologies of the time space series (psychrometric models, bi-dimensional phase space and spatial interpolation) allowed quantifying the process variability of the supervised process both from the dynamic and spatial points of view; as well as the identification of events. Thus, building additional tools to aid decision-making on process control brought the innovative application of the bi-dimensional representation of phase spaces in the study of time-space series of environmental variables in agri-food applications, an approach that had not been taken before. This thesis also wanted to show the potential of a control system based on specialized knowledge such as the fuzzy logic system. Firstly, moisture content estimation models and semantic rules directing the control process have been developed, the best model has been selected by an drying assay performed on hydrogel beads as food model; and finally the model has been validated through an assay in which carrot sheets were dehydrated. The results suggested that the control system developed is able to cope with difficulties such as changes in temperature daytime and nighttime, getting a product with good quality features comparable to those features achieved without applying any control over the operation and thus decreasing consumption energy by 98% compared to the same uncontrolled process. Instrumentation and data analysis methodologies implemented in this thesis have proved sufficiently versatile and cross-cutting to apply to several agri-food processes in which the temperature and relative humidity are the control criteria in those processes, having a direct effect on the industry sector.