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.

On the set of eigenvalues of a class of equimodular matrices

The structure of the set ϐ(A) of all eigenvalues of all complex matrices (elementwise) equimodular with a given n x n non-negative matrix A is studied. The problem was suggested by O. Taussky and some aspects have been studied by R. S. Varga and B.W. Levinger.

If every matrix equimodular with A is non-singular, then A is called regular. A new proof of the P. Camion-A.J. Hoffman characterization of regular matrices is given.

The set ϐ(A) consists of m ≤ n closed annuli centered at the origin. Each gap, ɤ, in this set can be associated with a class of regular matrices with a (unique) permutation, π(ɤ). The association depends on both the combinatorial structure of A and the size of the a_ii. Let A be associated with the set of r permutations, π₁, π₂,…, π_r, where each gap in ϐ(A) is associated with one of the π_k. Then r ≤ n, even when the complement of ϐ(A) has n+1 components. Further, if π(ɤ) is the identity, the real boundary points of ɤ are eigenvalues of real matrices equimodular with A. In particular, if A is essentially diagonally dominant, every real boundary point of ϐ(A) is an eigenvalues of a real matrix equimodular with A.

Several conjectures based on these results are made which if verified would constitute an extension of the Perron-Frobenius Theorem, and an algebraic method is introduced which unites the study of regular matrices with that of ϐ(A).

Normal structures and automorphism groups of t-designs

Combinatorial configurations known as t-designs are studied. These are pairs ˂B, ∏˃, where each element of B is a k-subset of ∏, and each t-design occurs in exactly λ elements of B, for some fixed integers k and λ. A theory of internal structure of t-designs is developed, and it is shown that any t-design can be decomposed in a natural fashion into a sequence of “simple” subdesigns. The theory is quite similar to the analysis of a group with respect to its normal subgroups, quotient groups, and homomorphisms. The analogous concepts of normal subdesigns, quotient designs, and design homomorphisms are all defined and used.

This structure theory is then applied to the class of t-designs whose automorphism groups are transitive on sets of t points. It is shown that if G is a permutation group transitive on sets of t letters and ф is any set of letters, then images of ф under G form a t-design whose parameters may be calculated from the group G. Such groups are discussed, especially for the case t = 2, and the normal structure of such designs is considered. Theorem 2.2.12 gives necessary and sufficient conditions for a t-design to be simple, purely in terms of the automorphism group of the design. Some constructions are given.

Finally, 2-designs with k = 3 and λ = 2 are considered in detail. These designs are first considered in general, with examples illustrating some of the configurations which can arise. Then an attempt is made to classify all such designs with an automorphism group transitive on pairs of points. Many cases are eliminated of reduced to combinations of Steiner triple systems. In the remaining cases, the simple designs are determined to consist of one infinite class and one exceptional case.

Towards in situ Single Cell Systems Biology

Systems-level studies of biological systems rely on observations taken at a resolution lower than the essential unit of biology, the cell. Recent technical advances in DNA sequencing have enabled measurements of the transcriptomes in single cells excised from their environment, but it remains a daunting technical problem to reconstruct in situ gene expression patterns from sequencing data. In this thesis I develop methods for the routine, quantitative in situ measurement of gene expression using fluorescence microscopy.

The number of molecular species that can be measured simultaneously by fluorescence microscopy is limited by the pallet of spectrally distinct fluorophores. Thus, fluorescence microscopy is traditionally limited to the simultaneous measurement of only five labeled biomolecules at a time. The two methods described in this thesis, super-resolution barcoding and temporal barcoding, represent strategies for overcoming this limitation to monitor expression of many genes in a single cell. Super-resolution barcoding employs optical super-resolution microscopy (SRM) and combinatorial labeling via-smFISH (single molecule fluorescence in situ hybridization) to uniquely label individual mRNA species with distinct barcodes resolvable at nanometer resolution. This method dramatically increases the optical space in a cell, allowing a large numbers of barcodes to be visualized simultaneously. As a proof of principle this technology was used to study the S. cerevisiae calcium stress response. The second method, sequential barcoding, reads out a temporal barcode through multiple rounds of oligonucleotide hybridization to the same mRNA. The multiplexing capacity of sequential barcoding increases exponentially with the number of rounds of hybridization, allowing over a hundred genes to be profiled in only a few rounds of hybridization.

The utility of sequential barcoding was further demonstrated by adapting this method to study gene expression in mammalian tissues. Mammalian tissues suffer both from a large amount of auto-fluorescence and light scattering, making detection of smFISH probes on mRNA difficult. An amplified single molecule detection technology, smHCR (single molecule hairpin chain reaction), was developed to allow for the quantification of mRNA in tissue. This technology is demonstrated in combination with light sheet microscopy and background reducing tissue clearing technology, enabling whole-organ sequential barcoding to monitor in situ gene expression directly in intact mammalian tissue.

The methods presented in this thesis, specifically sequential barcoding and smHCR, enable multiplexed transcriptional observations in any tissue of interest. These technologies will serve as a general platform for future transcriptomic studies of complex tissues.

Proposição e análise de modelos híbridos para o problema de escalonamento de produção em oficina de máquinas

Nas últimas décadas, o problema de escalonamento da produção em oficina de máquinas, na literatura referido como JSSP (do inglês Job Shop Scheduling Problem), tem recebido grande destaque por parte de pesquisadores do mundo inteiro. Uma das razões que justificam tamanho interesse está em sua alta complexidade. O JSSP é um problema de análise combinatória classificado como NP-Difícil e, apesar de existir uma grande variedade de métodos e heurísticas que são capazes de resolvê-lo, ainda não existe hoje nenhum método ou heurística capaz de encontrar soluções ótimas para todos os problemas testes apresentados na literatura. A outra razão basea-se no fato de que esse problema encontra-se presente no diaa- dia das indústrias de transformação de vários segmento e, uma vez que a otimização do escalonamento pode gerar uma redução significativa no tempo de produção e, consequentemente, um melhor aproveitamento dos recursos de produção, ele pode gerar um forte impacto no lucro dessas indústrias, principalmente nos casos em que o setor de produção é responsável por grande parte dos seus custos totais. Entre as heurísticas que podem ser aplicadas à solução deste problema, o Busca Tabu e o Multidão de Partículas apresentam uma boa performance para a maioria dos problemas testes encontrados na literatura. Geralmente, a heurística Busca Tabu apresenta uma boa e rápida convergência para pontos ótimos ou subótimos, contudo esta convergência é frequentemente interrompida por processos cíclicos e a performance do método depende fortemente da solução inicial e do ajuste de seus parâmetros. A heurística Multidão de Partículas tende a convergir para pontos ótimos, ao custo de um grande esforço computacional, sendo que sua performance também apresenta uma grande sensibilidade ao ajuste de seus parâmetros. Como as diferentes heurísticas aplicadas ao problema apresentam pontos positivos e negativos, atualmente alguns pesquisadores começam a concentrar seus esforços na hibridização das heurísticas existentes no intuito de gerar novas heurísticas híbridas que reúnam as qualidades de suas heurísticas de base, buscando desta forma diminuir ou mesmo eliminar seus aspectos negativos. Neste trabalho, em um primeiro momento, são apresentados três modelos de hibridização baseados no esquema geral das Heurísticas de Busca Local, os quais são testados com as heurísticas Busca Tabu e Multidão de Partículas. Posteriormente é apresentada uma adaptação do método Colisão de Partículas, originalmente desenvolvido para problemas contínuos, onde o método Busca Tabu é utilizado como operador de exploração local e operadores de mutação são utilizados para perturbação da solução. Como resultado, este trabalho mostra que, no caso dos modelos híbridos, a natureza complementar e diferente dos métodos Busca Tabu e Multidão de Partículas, na forma como são aqui apresentados, da origem à algoritmos robustos capazes de gerar solução ótimas ou muito boas e muito menos sensíveis ao ajuste dos parâmetros de cada um dos métodos de origem. No caso do método Colisão de Partículas, o novo algorítimo é capaz de atenuar a sensibilidade ao ajuste dos parâmetros e de evitar os processos cíclicos do método Busca Tabu, produzindo assim melhores resultados.

Structural Synthesis of 3-DoF Spatial Fully Parallel Manipulators

In this paper, the architectures of three degrees of freedom (3-DoF) spatial, fully parallel manipulators (PMs), whose limbs are structurally identical, are obtained systematically. To do this, the methodology followed makes use of the concepts of the displacement group theory of rigid body motion. This theory works with so-called 'motion generators'. That is, every limb is a kinematic chain that produces a certain type of displacement in the mobile platform or end-effector. The laws of group algebra will determine the actual motion pattern of the end-effector. The structural synthesis is a combinatorial process of different kinematic chains' topologies employed in order to get all of the 3-DoF motion pattern possibilities in the end-effector of the fully parallel manipulator.

Metaheurística para o Problema de Planejamento de Redes de Transmissão de Energia Elétrica com Redimensionamento

Com o passar do tempo, a demanda elétrica de diversas áreas varia tornando necessária a construção de novos geradores elétricos e a expansão da rede de transmissão de energia elétrica. Nesta dissertação, focamos no problema de expansão da rede de transmissão, assumindo que novos geradores estão construídos para suprir as novas demandas. Essa expansão exige altos investimentos que precisam ser cuidadosamente planejados. O problema pode ser modelado como um problema de otimização não linear inteira mista e pertence à classe dos problemas NP-difíceis. Desta forma, uma abordagem heurística pode ser adequada para a sua solução pois pode vir a fornecer boas soluções em tempo computacional aceitável. Esta dissertação se propõe a apresentar um estudo do problema de planejamento da expansão de redes de transmissão de energia elétrica estático e multiestágio. Mostramos o que já existe na literatura para o que é chamado de problema sem redimensionamento e as inovações feitas por nós para o problema com redimensionamento. Quanto aos métodos de solução, utilizamos a metaheurística GRASP para o problema estático e combinamos o GRASP com o procedimento Backward-Forward quando falamos em problema multiestágio. Nesta dissertação comparamos os resultados computacionais obtidos com resultados encontrados na literatura.

Physico-chemical interactions between compartment-forming lipids and other prebiotically relevant biomolecules

Lipids are essential constituents of contemporary living cells, serving as structural molecules that are necessary to form membranous compartments. Amphiphilic lipid-like molecules may also have contributed to prebiotic chemical evolution by promoting the synthesis, aggregation and cooperative encapsulation of other biomolecules. The resulting compartments would allow systems of molecules to be maintained that represent microscopic experiments in a natural version of combinatorial chemistry. Here we address these possibilities and describe recent results related to interactions between amphiphiles and other biomolecules during early evolution toward the first living cells.

Implementação distribuída de auto-cura em redes inteligentes de distribuição de energia elétrica utilizando árvores de extensão mínima.

A propriedade de auto-cura, em redes inteligente de distribuição de energia elétrica, consiste em encontrar uma proposta de reconfiguração do sistema de distribuição com o objetivo de recuperar parcial ou totalmente o fornecimento de energia aos clientes da rede, na ocorrência de uma falha na rede que comprometa o fornecimento. A busca por uma solução satisfatória é um problema combinacional cuja complexidade está ligada ao tamanho da rede. Um método de busca exaustiva se torna um processo muito demorado e muitas vezes computacionalmente inviável. Para superar essa dificuldade, pode-se basear nas técnicas de geração de árvores de extensão mínima do grafo, representando a rede de distribuição. Porém, a maioria dos estudos encontrados nesta área são implementações centralizadas, onde proposta de reconfiguração é obtida por um sistema de supervisão central. Nesta dissertação, propõe-se uma implementação distribuída, onde cada chave da rede colabora na elaboração da proposta de reconfiguração. A solução descentralizada busca uma redução no tempo de reconfiguração da rede em caso de falhas simples ou múltiplas, aumentando assim a inteligência da rede. Para isso, o algoritmo distribuído GHS é utilizado como base na elaboração de uma solução de auto-cura a ser embarcada nos elementos processadores que compõem as chaves de comutação das linhas da rede inteligente de distribuição. A solução proposta é implementada utilizando robôs como unidades de processamento que se comunicam via uma mesma rede, constituindo assim um ambiente de processamento distribuído. Os diferentes estudos de casos testados mostram que, para redes inteligentes de distribuição compostas por um único alimentador, a solução proposta obteve sucesso na reconfiguração da rede, indiferentemente do número de falhas simultâneas. Na implementação proposta, o tempo de reconfiguração da rede não depende do número de linhas nela incluídas. A implementação apresentou resultados de custo de comunicação e tempo dentro dos limites teóricos estabelecidos pelo algoritmo GHS.

Combinatória: abordagem precisa

O objetivo central deste projeto é precisar matematicamente certos objetos combinatórios que servem como ponto de partida nas apresentações usuais da Análise Combinatória e são comumente apresentados de maneira informal e intuitiva. Estabelecido este referencial teórico preciso, pretendemos, a partir dele, reapresentar os conceitos de Análise Combinatória de modo mais rigoroso privilegiando sempre a apresentação mais natural possível. Mais precisamente, estaremos interessados em reapresentar os resultados referentes ao capítulo dois do livro do professor Augusto C. Morgado a partir de uma versão matematicamente mais precisa dos Princípios Aditivo e Multiplicativo. Além disso, pretendemos que os argumentos usados em nossas deduções usem predominantemente indução ou construção de bijeções, o que é um dos grandes objetos de estudo da combinatória moderna

在体大鼠海马Schaffer-CA1条件化双通路与海马组合突触可塑性

在戊巴比妥钠麻醉的Sprague-Dawley大鼠上,运用海马Schaffer-CA1双通路条件化作用(低频配对,600对脉冲,5Hz,配对刺激相应的兴奋性突触后电位峰值时间间隔为10ms)在两条Schaffer-CA1条件化通路上同时诱导出突触可塑性,呈现出海马组合突触可塑性.结果显示:不管海马Schaffer-CA1双通路独立与否,双通路条件化作用均可以同时诱导出长时程增强(long-term potentiation,LTP)和长时程抑制(long-term depression,LTD),呈现出LTP/LTD组合突触可塑性.结果表明:海马Schaffer-CA1双通路技术,可实现海马突触可塑性的双向诱导,可塑性的方向取决于突触的自身状态.由此提示,与传统的高频诱导LTP低频诱导LTD相比,在海马Schaffer-CA1双通路条件化作用诱导出的组合突触可塑性可以吏好地编码海马相关的学习记忆,体现了海马突触可塑性的灵活性与稳定性.

Simulated Annealing: Rigorous finite-time guarantees for optimization on continuous domains

Simulated annealing is a popular method for approaching the solution of a global optimization problem. Existing results on its performance apply to discrete combinatorial optimization where the optimization variables can assume only a finite set of possible values. We introduce a new general formulation of simulated annealing which allows one to guarantee finite-time performance in the optimization of functions of continuous variables. The results hold universally for any optimization problem on a bounded domain and establish a connection between simulated annealing and up-to-date theory of convergence of Markov chain Monte Carlo methods on continuous domains. This work is inspired by the concept of finite-time learning with known accuracy and confidence developed in statistical learning theory.

Towards productivity indicators for performance-based façade design in commercial buildings

Decision-making in the façade design process has a significant influence on several aspects of indoor environment, thereby making it a complex and multi-objective optimisation process. There are two principal barriers in the process of indentifying an optimal façade solution. Firstly, most existing indoor environmental evaluation methods do not account for all the indoor environmental quality (IEQ) aspects relevant to façade design. Secondly, the relationship between the physical properties of a particular façade design option and the resulting economic benefits accrued during its service-life is unknown. In this paper, we introduce the bases for establishing relationships between occupant productivity and the combinatorial effects of four key façade-related IEQ aspects, namely, thermal comfort, aural comfort, visual comfort and air quality, on occupant productivity. The proposed framework's potential is tested against seven existing experimental investigations and its applicability is illustrated by a simple façade design example. The proposed approach ultimately aims to provide a quantitative economic measure of alternative façade design options that would be applicable to early design stage. Aspects of the work that require further experimental validation are identified. © 2012 Elsevier Ltd.

组合测试:原理与方法

组合测试能够在保证错误检出率的前提下采用较少的测试用例测试系统.但是,组合测试用例集的构造问题的复杂度是NP完全的.组合测试方法的有效性和复杂性吸引了组合数学领域和软件工程领域的学者们对其进行深入的研究.总结了近年来在组合测试方面的研究进展,主要内容包括:组合测试准则的研究、组合测试生成问题与其他NP完全问题的联系、组合测试用例的数学构造方法、采用计算机搜索的组合测试生成方法以及基于组合测试的错误定位技术.

海马突触可塑性与异常记忆

5-羟色胺(5-HT)是中枢神经系统内非常重要的神经递质，广泛参与各种行为和生理过程。5-羟色胺功能低下可导致多种精神类疾病尤其是焦虑、抑郁和创伤后应激障碍等，而这些疾病都伴有学习和记忆的障碍；海马是参与学习记忆的重要脑区。海马接受5-HT神经元的直接投射且富含5-HT受体，因而海马也可以通过5-HT系统调控焦虑、抑郁及学习记忆。海马突触可塑性是学习记忆的细胞分子机制，是学习记忆的基础。我们条件性敲除转录因子Lmx1b得到中枢5-HT缺失小鼠，利用该小鼠进行中枢神经系统5-HT功能的研究。我们发现该小鼠的脑结构和运动能力正常；水迷宫空间学习能力正常，但空间记忆受损；焦虑水平降低，但是环境恐惧学习和记忆能力增强，增强的恐惧记忆能被外源给予的5-HT逆转；在中枢5-HT缺失小鼠中，应激对海马可塑性的作用即损伤LTP易化LTD消失，外源给予5-HT可以恢复应激的效果。这些结果提示应激导致海马LTP损伤可能是保护机制，缺乏这种保护机制可能导致恐惧记忆相关的创伤后应激障碍(PTSD)的易感。成瘾的核心特征是对药物的强迫性渴求和复吸。成瘾与学习记忆有很多共同的脑区和分子通路，它可能通过篡夺正常生理神经通路而产生比正常生理反应更强烈的可塑性，形成有害的异常记忆。以前的报道证实海马的兴奋性突触可塑性在成瘾过程中的适应性改变可能是成瘾的机制；但是成瘾涉及复杂的生物机制，因而不可能仅是兴奋性突触可塑性的贡献。我们研究了5-HT系统和抑制性系统（主要是GABA能系统）在成瘾中的贡献。利用中枢5-HT缺失小鼠，我们发现5-HT缺失小鼠的吗啡显著地易化了5-HT CKO的海马LTP，同时也导致成瘾行为持续不消退；5-HT和5-HT1a受体激动剂能逆转此现象。这提示毒品成瘾可能导致中枢5-HT缺失，进而增强海马LTP，使毒品相关记忆牢固不消退。GABA能系统是中枢神经系统最重要的抑制性系统，我们研究发现一次吗啡对内源性大麻受体（CB1R）依赖的抑制性突触的长时程抑制（Inhibitory long-term depression，I-LTD）没有影响，成瘾后I-LTD抑制，而吗啡成瘾后戒断导致了内源性大麻受体(CB1R)和L-型钙通道(LTCC)依赖的GABA能LTD (I-LTD)，使I-LTD增大了一倍，提示在吗啡成瘾阶段过程中，有组合突触可塑性发生，进而增强了突触可塑性的调控范围。 本论文是对中枢5-HT系统对海马兴奋性突触可塑性在焦虑、应激、成瘾等异常记忆中的调节作用以及海马抑制性系统在成瘾和戒断中的贡献进行研究，表明恐惧记忆和毒品成瘾记忆存在许多共同的细胞分子机理，对今后治疗焦虑、创伤后应激障碍和成瘾提供了新的思路。