Topics in randomized numerical linear algebra

This thesis studies three classes of randomized numerical linear algebra algorithms, namely: (i) randomized matrix sparsification algorithms, (ii) low-rank approximation algorithms that use randomized unitary transformations, and (iii) low-rank approximation algorithms for positive-semidefinite (PSD) matrices.

Randomized matrix sparsification algorithms set randomly chosen entries of the input matrix to zero. When the approximant is substituted for the original matrix in computations, its sparsity allows one to employ faster sparsity-exploiting algorithms. This thesis contributes bounds on the approximation error of nonuniform randomized sparsification schemes, measured in the spectral norm and two NP-hard norms that are of interest in computational graph theory and subset selection applications.

Low-rank approximations based on randomized unitary transformations have several desirable properties: they have low communication costs, are amenable to parallel implementation, and exploit the existence of fast transform algorithms. This thesis investigates the tradeoff between the accuracy and cost of generating such approximations. State-of-the-art spectral and Frobenius-norm error bounds are provided.

The last class of algorithms considered are SPSD "sketching" algorithms. Such sketches can be computed faster than approximations based on projecting onto mixtures of the columns of the matrix. The performance of several such sketching schemes is empirically evaluated using a suite of canonical matrices drawn from machine learning and data analysis applications, and a framework is developed for establishing theoretical error bounds.

In addition to studying these algorithms, this thesis extends the Matrix Laplace Transform framework to derive Chernoff and Bernstein inequalities that apply to all the eigenvalues of certain classes of random matrices. These inequalities are used to investigate the behavior of the singular values of a matrix under random sampling, and to derive convergence rates for each individual eigenvalue of a sample covariance matrix.

Geometric elasticity for graphics, simulation, and computation

We develop new algorithms which combine the rigorous theory of mathematical elasticity with the geometric underpinnings and computational attractiveness of modern tools in geometry processing. We develop a simple elastic energy based on the Biot strain measure, which improves on state-of-the-art methods in geometry processing. We use this energy within a constrained optimization problem to, for the first time, provide surface parameterization tools which guarantee injectivity and bounded distortion, are user-directable, and which scale to large meshes. With the help of some new generalizations in the computation of matrix functions and their derivative, we extend our methods to a large class of hyperelastic stored energy functions quadratic in piecewise analytic strain measures, including the Hencky (logarithmic) strain, opening up a wide range of possibilities for robust and efficient nonlinear elastic simulation and geometry processing by elastic analogy.

Efficient methods for stochastic optimal control

The Hamilton Jacobi Bellman (HJB) equation is central to stochastic optimal control (SOC) theory, yielding the optimal solution to general problems specified by known dynamics and a specified cost functional. Given the assumption of quadratic cost on the control input, it is well known that the HJB reduces to a particular partial differential equation (PDE). While powerful, this reduction is not commonly used as the PDE is of second order, is nonlinear, and examples exist where the problem may not have a solution in a classical sense. Furthermore, each state of the system appears as another dimension of the PDE, giving rise to the curse of dimensionality. Since the number of degrees of freedom required to solve the optimal control problem grows exponentially with dimension, the problem becomes intractable for systems with all but modest dimension.

In the last decade researchers have found that under certain, fairly non-restrictive structural assumptions, the HJB may be transformed into a linear PDE, with an interesting analogue in the discretized domain of Markov Decision Processes (MDP). The work presented in this thesis uses the linearity of this particular form of the HJB PDE to push the computational boundaries of stochastic optimal control.

This is done by crafting together previously disjoint lines of research in computation. The first of these is the use of Sum of Squares (SOS) techniques for synthesis of control policies. A candidate polynomial with variable coefficients is proposed as the solution to the stochastic optimal control problem. An SOS relaxation is then taken to the partial differential constraints, leading to a hierarchy of semidefinite relaxations with improving sub-optimality gap. The resulting approximate solutions are shown to be guaranteed over- and under-approximations for the optimal value function. It is shown that these results extend to arbitrary parabolic and elliptic PDEs, yielding a novel method for Uncertainty Quantification (UQ) of systems governed by partial differential constraints. Domain decomposition techniques are also made available, allowing for such problems to be solved via parallelization and low-order polynomials.

The optimization-based SOS technique is then contrasted with the Separated Representation (SR) approach from the applied mathematics community. The technique allows for systems of equations to be solved through a low-rank decomposition that results in algorithms that scale linearly with dimensionality. Its application in stochastic optimal control allows for previously uncomputable problems to be solved quickly, scaling to such complex systems as the Quadcopter and VTOL aircraft. This technique may be combined with the SOS approach, yielding not only a numerical technique, but also an analytical one that allows for entirely new classes of systems to be studied and for stability properties to be guaranteed.

The analysis of the linear HJB is completed by the study of its implications in application. It is shown that the HJB and a popular technique in robotics, the use of navigation functions, sit on opposite ends of a spectrum of optimization problems, upon which tradeoffs may be made in problem complexity. Analytical solutions to the HJB in these settings are available in simplified domains, yielding guidance towards optimality for approximation schemes. Finally, the use of HJB equations in temporal multi-task planning problems is investigated. It is demonstrated that such problems are reducible to a sequence of SOC problems linked via boundary conditions. The linearity of the PDE allows us to pre-compute control policy primitives and then compose them, at essentially zero cost, to satisfy a complex temporal logic specification.

Cidades secas, vidas secas: A trajetória das águas e sua regulamentação no Rio de Janeiro sob uma perspectiva urbano-ambiental

Esta tese analisará a distribuição das águas na cidade do Rio de Janeiro considerando os elementos sociais, jurídicos, políticos, e seus reflexos no direito urbano e ambiental. Nesse aspecto referenciará as medidas de regulação e de organização da estrutura urbana, desde a formação da cidade até os dias atuais, assim como as consequências da exclusão e da ausência das políticas urbanas equitativas. No início, as ocupações irregulares, se distantes do centro e dos bairros elitizados, não despertavam maiores demandas do poder público, porém com o aumento das periferias e as ocupações próximas aos bairros formais, inúmeras medidas adotadas optaram pela remoção, contenção e a destruição dos espaços sem apresentar uma solução, agravando os problemas urbanos. Tais problemas, reconhecidamente sociais, passam a ser denominados urbanos e ambientais, gerando uma complexa criminalização dos moradores das periferias. As intervenções nos espaços são legalizadas pelo instrumento jurídico, as residências suburbanas são classificadas como ilegais e, por consequência, os recursos que deveriam atender a todos na cidade são direcionados apenas para cidade legalizada, criando a celeuma da desigualdade. Assim, amontoados em barracos precários, sem abastecimento de água, energia, esgoto e coleta de lixo, as periferias multiplicam as diversas formas de violência, uma vez que o direito não socorre esses moradores que, abandonados pela lei, vivem a escassez das águas e a especulação dos serviços ilegais de abastecimento. A crise do abastecimento não é causada pelas populações mais empobrecidas, mas pelo mercado que se apropria da maior parte desses recursos, dentro do sistema de uma lógica capitalista, e exclui aqueles que não podem pagar pelo abastecimento regular. Nesse sentido, este trabalho entende que o direito, ainda que tenha se tornado regulatório pode assumir um caráter revolucionário e transformador em que o direito das águas seja um direito da comunidade, por isso, um bem público não estatal, por fim objetiva esse trabalho estudar as leis das águas dentro do paradigma da solidariedade hídrica.

Damping and saturation of a second order electron plasma wave echo

A description is given of experimental work on the damping of a second order electron plasma wave echo due to velocity space diffusion in a low temperature magnetoplasma. Sufficient precision was obtained to verify the theoretically predicted cubic rather than quadratic or quartic dependence of the damping on exciter separation. Compared to the damping predicted for Coulomb collisions in a thermal plasma in an infinite magnetic field, the magnitude of the damping was approximately as predicted, while the velocity dependence of the damping was weaker than predicted. The discrepancy is consistent with the actual non-Maxwellian electron distribution of the plasma.

In conjunction with the damping work, echo amplitude saturation was measured as a function of the velocity of the electrons contributing to the echo. Good agreement was obtained with the predicted J₁ Bessel function amplitude dependence, as well as a demonstration that saturation did not influence the damping results.

The design of a controllable imaging device with the cold atomic medium

Under the circumstance of a Gaussian control field, the cold atomic medium with electromagnetically induced transparency (EIT) turns out to be the special medium with the quadratic index distribution which is controllable online. In our study, the optical system occupies a portion of the EIT medium which acts as an imaging device. With the help of the Collins formula, the analytic expression for the spatial distribution of the probe field in the cold atomic medium is obtained as well as the location of the imaging. The methods for improving the visibility of the imaging are proposed in this paper. Moreover, we also show that the shapes of the images on the output are strongly influenced by the intensity of the control field, which provides a potential optical processing method.

Desigualdades de género en los trabajos : el caso de la CAE.

Este trabajo analiza los avances logrados y las desigualdades existentes en el mercado laboral y en el trabajo no remunerado con respecto a las mujeres, con especial incidencia en la C.A. de Euskadi. En primer lugar, se reflexiona de forma general sobre las medidas promovidas desde distintos niveles: europeo, estatal y de la C.A. de Euskadi, y la evolución que ha ido experimentando la sociedad para fomentar la igualdad entre mujeres y hombres. En segundo lugar, se hace un recorrido a través de los análisis teóricos de la desigualdad. En tercer lugar, se analiza la situación laboral de las mujeres vascas en comparación con la de los hombres, con especial atención en el trabajo no remunerado, la actividad laboral, el paro y los salarios. Finalmente, quedan planteadas una serie de conclusiones a las que se llega tras realizar el análisis.

二次光栅在波前测量中的应用

采用一种特殊的二次光栅用于激光波前测量, 它对非零级衍射光束具有不同的聚焦效应, 其光栅线为圆弧型而非直线。导出了在会聚光束情况下的两平面成像在单一像平面上的距离关系, 实验上实现了二次光栅用于会聚光束的波前测量, 测量得到会聚光束具有较大的散焦(-2.93λ)和球差(1.34λ), 与该透镜引起波前的离焦像差理论理想值(-2.695λ)基本符合。该技术可以实现波前的高空间分辨力和高精度实时测量, 大大减少光学元件数量, 降低装置成本。由于大功率激光束的不稳定性, 其波前变化非常快, 所以该方法的实时性非

合成孔径激光成像雷达(Ⅰ):离焦和相位偏置望远镜接收天线

把合成孔径激光成像雷达的目标衍射区分为三个区域,提出采用离焦或者附加空间相位调制板的光学接收望远镜补偿回波像差。当目标处于菲涅耳衍射区时可采用离焦或偏置望远镜补偿回波二次项离焦像差并产生用于孔径合成的二次项相位历程;目标处于夫琅和费衍射区时可以采用离焦或偏置望远镜补偿回波二次项离焦像差但不产生相位历程;目标处于瑞利-索末菲衍射区域时不可能补偿回波高阶像差。

合成孔径激光成像雷达(Ⅱ):空间相位偏置发射望远镜

报道一种可以进行空间相位偏置的光学望远镜,用作合成孔径激光成像雷达中的光学发射天线。在望远镜内放置相位调制平板,控制望远镜的离焦量和位相调制平板的相位函数,能够在激光望远镜的照明区产生可控制的附加空间相位二次项,灵活改变激光照明波前,以在目标回波接收信号中产生雷达运动方向上的所需的二次项相位历程,因此能够实现特定的方位向成像分辨率。

合成孔径激光成像雷达(Ⅲ):双向环路发射接收望远镜

提出了一种用于合成孔径激光成像雷达的双向环路结构的发射接收望远镜,双向环路包括发射4-f转像系统、接收4-f转像系统和独立的望远镜。发射通道中设置离焦和相位调制平板偏置,接收通道中设置离焦和相位平板偏置。控制发射离焦量,发射相位调制函数,接收离焦量,接收相位调制函数,用同一个望远镜可以同时实现空间二次项相位附加偏置的激光发射和消除目标点散射回波接收波面像差的离焦光学接收,并产生雷达运动方向上合适的和可控制的相位二次项历程,从而实现孔径合成成像。详细介绍了系统设计,给出了从发射到光电外差接收的全过程传输方程。

Uncovering the Lagrangian from observations of trajectories

We approach the problem of automatically modeling a mechanical system from data about its dynamics, using a method motivated by variational integrators. We write the discrete Lagrangian as a quadratic polynomial with varying coefficients, and then use the discrete Euler-Lagrange equations to numerically solve for the values of these coefficients near the data points. This method correctly modeled the Lagrangian of a simple harmonic oscillator and a simple pendulum, even with significant measurement noise added to the trajectories.

A gestão estadual do SUS em Minas Gerais e seu efeito na regionalização e em alguns resultados de saúde da população

Este estudo aborda a atuação da gestão estadual do Serviço Único de Saúde (SUS) sobre o quadro de desigualdades em saúde, analisando o caso do estado de Minas Gerais. A descentralização dos serviços de saúde, no âmbito do federalismo brasileiro, promoveu o ingresso de recursos em todos os municípios, permitindo a incorporação de cidadãos de todas as regiões do país ao sistema. Ao mesmo tempo, a pulverização dos recursos perpetuou as históricas desigualdades ao acesso a serviços de mais complexidade. Esse quadro exige a intervenção do nível estadual para ser alterado. Este é o tema deste trabalho, que analisou o processo de regionalização da assistência à saúde, no período de 2002 a 2009, sob a coordenação da gestão estadual do SUS em Minas Gerais, considerando o cenário federativo brasileiro, em que os municípios são entes autônomos. Os objetivos específicos foram: descrever o processo de regionalização proposto pela gestão estadual para alcançar a melhoria dos serviços públicos e a redução de desigualdades regionais; verificar a extensão da implementação da regionalização nas microrregiões, tomando como referência o gasto de recursos estaduais dirigidos a municípios e a implantação das Comissões Intergestores Bipartites Microrregionais e Macrorregionais; avaliar o efeito da regionalização na rede de serviços e na redução das desigualdades regionais, relativas a recursos, acesso a serviços e em algumas condições de saúde da população, consideradas sensíveis à regionalização. Revisou-se a literatura sobre federalismo, descentralização e relações intergovernamentais e documentos oficiais; utilizaram-se dados secundários sobre recursos e indicadores de saúde e de desenvolvimento. Verificou-se que o processo foi viabilizado por intensa aproximação entre governo estadual e municípios; por uma proposta consistente e pelo aporte de recursos. Constatou-se, ainda, que, no período, ampliou-se o acesso a leitos de Unidade de Terapia Intensiva (UTI) e a mamografias; houve desconcentração de recursos e equipamentos na direção de macrorregiões e microrregiões mais desprovidas; os recursos estaduais disciplinaram o gasto federal; e reduziram-se as desigualdades entre as microrregiões em relação a: indicadores socioeconômicos, recursos federais e estaduais, acesso a mamografias e mortalidade por doenças cardiovasculares.

基于PLZT的电光偏转器的特性研究

采用具有高二次电光效应的掺镧锆钛酸铅陶瓷材料（PLZT），设计和制备了一种基于折射率随外加电压发生变化的电光偏转器。构建了测试系统，测得PLZT的电光系数是R33=2.1

Do salvacionismo à segregação: a experiência dos Centros Integrados de Educação Pública no Rio de Janeiro

Este trabalho versa sobre a relação entre a implantação de um projeto de educação pública e a sua receptividade social. Resgata as concepções que deram origem ao programa de implantação das escolas de tempo integral no estado do Rio de Janeiro e como hoje elas são vistas por seus usuários. Discute os resultados inesperados que teve o projeto educacional salvador (não só da educação como também das populações empobrecidas do estado do Rio de Janeiro). Pretendendo ser inclusivo, dando ao pobre acesso a benefícios que não tinha, produziu mais segregação, repetindo a seletividade que a escola pública brasileira apresenta.