Convex analysis for minimizing and learning submodular set functions

The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions.

First, we develop a novel method for minimizing a particular class of submodular functions, which can be expressed as a sum of concave functions composed with modular functions. The basic algorithm uses an accelerated first order method applied to a smoothed version of its convex extension. The smoothing algorithm is particularly novel as it allows us to treat general concave potentials without needing to construct a piecewise linear approximation as with graph-based techniques.

Second, we derive the general conditions under which it is possible to find a minimizer of a submodular function via a convex problem. This provides a framework for developing submodular minimization algorithms. The framework is then used to develop several algorithms that can be run in a distributed fashion. This is particularly useful for applications where the submodular objective function consists of a sum of many terms, each term dependent on a small part of a large data set.

Lastly, we approach the problem of learning set functions from an unorthodox perspective---sparse reconstruction. We demonstrate an explicit connection between the problem of learning set functions from random evaluations and that of sparse signals. Based on the observation that the Fourier transform for set functions satisfies exactly the conditions needed for sparse reconstruction algorithms to work, we examine some different function classes under which uniform reconstruction is possible.

Oyster spat set on natural clutch in the Maryland portion of the Chesapeake Bay (1939 - 1975)

Basically this report is an attempt to document trends in oyster recruitment since 1939 and to relate those trends to the actual oyster harvest throughout the Maryland portion of the Chesapeake Bay. It is also hoped that the data as well as the charts compiled in this report will serve as a reference to aid in future studies on Chesapeake Bay oysters. A few if the major biological factors that affect the natural reproduction of the oyster and environmental degradations that may possibly affect oyster reproduction or harvest in the Chesapeake Bay are also briefly discussed. (PDF contains 32 pages)

Avaliação da estabilidade da cirurgia de avanço mandibular através da superposição de modelos tridimensionais

Embora a cirurgia de avanço mandibular seja considerada um procedimento altamente estável, existem algumas preocupações clínicas em relação a mudanças nos côndilos e nos segmentos proximais, que podem levar a recidiva sagital e abertura de mordida. A avaliação dos resultados da cirurgia através de ferramentas de geração e superposição de modelos virtuais tridimensionais (3D) permite a identificação e quantificação dos deslocamentos e remodelação óssea que podem ajudar a explicar as interações entre os componentes dentários, esqueléticos e de tecido mole que estão relacionados a resposta ao tratamento. Este estudo observacional prospectivo avaliou, através de tomografia computadorizada de feixe cônico (CBCT), mudanças na posição/remodelação 3D dos ramos mandibulares, côndilos e mento. Assim, exames CBCT de 27 pacientes foram adquiridos antes da cirurgia (T1), imediatamente após a cirurgia(T2), e 1 ano após a cirurgia(T3). Uma técnica automática de superposição na base do crânio foi utilizada para permitir a avaliação das mudanças ocorridas nas regiões anatômicas de interesse (RAI). Os deslocamentos foram visualizados e quantificados em mapas coloridos 3D através da ferramenta de linha de contorno (ISOLINE). Pelo teste t pareado compararam-se as mudanças entre T1-T2 e T2-T3. O coeficiente de correlação de Pearson verificou se os deslocamentos ocorridos nas RAI foram correlacionados entre si e entre os tempos de avaliação. O nível de significância foi determinado em 0,05. O avanço mandibular médio foi de 6,813,2mm em T2 e 6,363,41mm em T3 (p=0,13). Entre T2 e T3, a posição do mento variou positivamente (≥2mm) em 5 pacientes negativamente em 7. 12% dos pacientes sofreram recidivas ≥4mm. Para todas as outras RAI avaliadas, apenas a porção inferior dos ramos (lado direito - 2,342,35mm e lado esquerdo 2,972,71mm) sofreram deslocamentos médios >2mm com a cirurgia. No acompanhamento em longo prazo, esse deslocamento lateral da porção inferior dos ramos foi mantido (lado direito - 2,102,15mm, p=0,26; e lado esquerdo -2,762,80, p=0,46), bem como todos os outros deslocamentos observados (p>0,05). As mudanças na posição do mento foram correlacionadas a adaptações pós-cirúrgicas nos bordos posteriores dos ramos (esquerdo r=-0,73 e direito r=-0,68) e côndilos (esquerdo r=-0,53 e direito r=-0,46). Os deslocamentos médios sofridos pelas estruturas do lado esquerdo foram suavemente maiores do que no direito. Correlações dos deslocamentos ocorridos entre T1-T2 e T2-T3 mostraram que: os deslocamentos dos côndilos esquerdos com a cirurgia foram negativamente correlacionados às adaptações pós-cirúrgicas destes (r=-0,51); e que o deslocamento da porção superior do ramo esquerdo com a cirurgia foi correlacionado à adaptação pós-cirúrgica ocorrida nos bordos posteriores (r=0,39) e côndilos do mesmo lado (r=0,39). Pode-se concluir que: (1) os deslocamentos causados pela cirurgia foram de modo geral estáveis no acompanhamento de 1 ano, mas identificou-se uma considerável variação individual; (2) as mudanças pós-cirúrgicas na posição do mento foram correlacionadas a adaptações sofridas pelos côndilos e bordos posteriores dos ramos; e que (3) deslocamentos suavemente maiores causados pela cirurgia nas estruturas do lado esquerdo levaram a maiores adaptações pós-cirúrgicas no segmento proximal deste lado.

Free algebras in Von Neumann-Bernays-Gӧdel set theory and positive elementary inductions in reasonable structures

This thesis consists of two independent chapters. The first chapter deals with universal algebra. It is shown, in von Neumann-Bernays-Gӧdel set theory, that free images of partial algebras exist in arbitrary varieties. It follows from this, as set-complete Boolean algebras form a variety, that there exist free set-complete Boolean algebras on any class of generators. This appears to contradict a well-known result of A. Hales and H. Gaifman, stating that there is no complete Boolean algebra on any infinite set of generators. However, it does not, as the algebras constructed in this chapter are allowed to be proper classes. The second chapter deals with positive elementary inductions. It is shown that, in any reasonable structure ᶆ, the inductive closure ordinal of ᶆ is admissible, by showing it is equal to an ordinal measuring the saturation of ᶆ. This is also used to show that non-recursively saturated models of the theories ACF, RCF, and DCF have inductive closure ordinals greater than _ω.

Two-step digit-set-restricted modified signed-digit addition-subtraction algorithm and its optoelectronic implementation

A novel, to our knowledge, two-step digit-set-restricted modified signed-digit (MSD) addition-subtraction algorithm is proposed. With the introduction of the reference digits, the operand words are mapped into an intermediate carry word with all digits restricted to the set {(1) over bar, 0} and an intermediate sum word with all digits restricted to the set {0, 1}, which can be summed to form the final result without carry generation. The operation can be performed in parallel by use of binary logic. An optical system that utilizes an electron-trapping device is suggested for accomplishing the required binary logic operations. By programming of the illumination of data arrays, any complex logic operations of multiple variables can be realized without additional temporal latency of the intermediate results. This technique has a high space-bandwidth product and signal-to-noise ratio. The main structure can be stacked to construct a compact optoelectronic MSD adder-subtracter. (C) 1999 Optical Society of America.

One-step digit-set-restricted modified signed-digit adder using an incoherent correlator based on a shared content-addressable memory

An efficient one-step digit-set-restricted modified signed-digit (MSD) adder based on symbolic substitution is presented. In this technique, carry propagation is avoided by introducing reference digits to restrict the intermediate carry and sum digits to {1,0} and {0,1}, respectively. The proposed technique requires significantly fewer minterms and simplifies system complexity compared to the reported one-step MSD addition techniques. An incoherent correlator based on an optoelectronic shared content-addressable memory processor is suggested to perform the addition operation. In this technique, only one set of minterms needs to be stored, independent of the operand length. (C) 2002 society or Photo-Optical Instrumentation Engineers.

Efficient two-step digit-set-restricted modified signed-digit algorithm based on optoelectronic shared content-addressable memory

A two-step digit-set-restricted modified signed-digit (MSD) adder based on symbolic substitution is presented. In the proposed addition algorithm, carry propagation is avoided by using reference digits to restrict the intermediate MSD carry and sum digits into {(1) over bar ,0} and {0, 1}, respectively. The algorithm requires only 12 minterms to generate the final results, and no complementarity operations for nonzero outputs are involved, which simplifies the system complexity significantly. An optoelectronic shared content-addressable memory based on an incoherent correlator is used for experimental demonstration. (c) 2005 Society of Photo-Optical Instrumentation Engineers.

Efficient two-step digit-set-restricted modified signed-digit algorithm based on optoelectronic shared content-addressable memory

A two-step digit-set-restricted modified signed-digit (MSD) adder based on symbolic substitution is presented. In the proposed addition algorithm, carry propagation is avoided by using reference digits to restrict the intermediate MSD carry and sum digits into {(1) over bar ,0} and {0, 1}, respectively. The algorithm requires only 12 minterms to generate the final results, and no complementarity operations for nonzero outputs are involved, which simplifies the system complexity significantly. An optoelectronic shared content-addressable memory based on an incoherent correlator is used for experimental demonstration. (c) 2005 Society of Photo-Optical Instrumentation Engineers.

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).