Ives Macedo, PhD, DSc

Various applications in signal processing and machine learning give rise to highly structured spectral optimization problems characterized by low-rank solutions. Two important examples that motivate this work are optimization problems from phase retrieval and from blind deconvolution, which are designed to yield rank-1 solutions. An algorithm is described that is based on solving a certain constrained eigenvalue optimization problem that corresponds to the gauge dual which, unlike the more… Show more

Various applications in signal processing and machine learning give rise to highly structured spectral optimization problems characterized by low-rank solutions. Two important examples that motivate this work are optimization problems from phase retrieval and from blind deconvolution, which are designed to yield rank-1 solutions. An algorithm is described that is based on solving a certain constrained eigenvalue optimization problem that corresponds to the gauge dual which, unlike the more typical Lagrange dual, has an especially simple constraint. The dominant cost at each iteration is the computation of rightmost eigenpairs of a Hermitian operator. A range of numerical examples illustrate the scalability of the approach. Show less

The emergence of compressed sensing and its impact on various applications in signal processing and machine learning has sparked an interest in generalizing its concepts and techniques to inverse problems that involve quadratic measurements. Important recent developments borrow ideas from matrix lifting techniques in combinatorial optimization and result in convex optimization problems characterized by solutions with very low rank, and by linear operators that are best treated with matrix-free… Show more

The emergence of compressed sensing and its impact on various applications in signal processing and machine learning has sparked an interest in generalizing its concepts and techniques to inverse problems that involve quadratic measurements. Important recent developments borrow ideas from matrix lifting techniques in combinatorial optimization and result in convex optimization problems characterized by solutions with very low rank, and by linear operators that are best treated with matrix-free approaches. Typical applications give rise to enormous optimization problems that challenge even the very best workhorse algorithms and numerical solvers for semidefinite programming. The work presented in this thesis focuses on the class of low-rank spectral optimization problems and its connection with a theoretical duality framework for gauge functions introduced in a seminal paper by Freund (1987). We begin by exploring the theory of gauge duality focusing on a slightly specialized structure often encountered in the motivating inverse problems. What follows is a connection of this framework with two important classes of spectral optimization problems commonly found in the literature: trace minimization in the cone of positive semidefinite matrices and affine nuclear norm minimization. This leads us to a convex eigenvalue optimization problem with rather simple constraints, and involving a number of variables equal to the number of measurements, thus with dimension far smaller than the primal. The last part of this thesis exploits a sense of strong duality between the primal-dual pair of gauge problems to characterize their solutions and to devise a method for retrieving a primal minimizer from a dual one. This allows us to design and implement a proof of concept solver which compares favorably against solvers designed specifically for the PhaseLift formulation of the celebrated phase recovery problem and a scenario of blind image deconvolution. Show less

Gauge functions significantly generalize the notion of a norm, and gauge optimization, as defined by [R. M. Freund, Math. Programming, 38 (1987), pp. 47--67], seeks the element of a convex set that is minimal with respect to a gauge function. This conceptually simple problem can be used to model a remarkable array of useful problems, including a special case of conic optimization, and related problems that arise in machine learning and signal processing. The gauge structure of these problems… Show more

Gauge functions significantly generalize the notion of a norm, and gauge optimization, as defined by [R. M. Freund, Math. Programming, 38 (1987), pp. 47--67], seeks the element of a convex set that is minimal with respect to a gauge function. This conceptually simple problem can be used to model a remarkable array of useful problems, including a special case of conic optimization, and related problems that arise in machine learning and signal processing. The gauge structure of these problems allows for a special kind of duality framework. This paper explores the duality framework proposed by Freund, and proposes a particular form of the problem that exposes some useful properties of the gauge optimization framework (such as the variational properties of its value function), and yet maintains most of the generality of the abstract form of gauge optimization. Show less

In this work we investigate a generalized interpolation approach using radial basis functions to reconstruct implicit surfaces from polygonal meshes. With this method, the user can define with great flexibility three sets of constraint interpolants: points, normals, and tangents; allowing to balance computational complexity, precision, and feature modeling. Furthermore, this flexibility makes possible to avoid untrustworthy information, such as normals estimated on triangles with bad aspect… Show more

In this work we investigate a generalized interpolation approach using radial basis functions to reconstruct implicit surfaces from polygonal meshes. With this method, the user can define with great flexibility three sets of constraint interpolants: points, normals, and tangents; allowing to balance computational complexity, precision, and feature modeling. Furthermore, this flexibility makes possible to avoid untrustworthy information, such as normals estimated on triangles with bad aspect ratio. We present results of the method for applications related to the problem of modeling 2D curves from polygons and 3D surfaces from polygonal meshes. We also apply the method to problems involving subdivision surfaces and front-tracking of moving boundaries. Finally, as our technique generalizes the recently proposed HRBF Implicits technique, comparisons with this approach are also conducted. Show less

While current image deformation methods are careful in making the new geometry seem right, little attention has been given to the photometric aspects. We introduce a deformation method that results in coherently illuminated objects. For this task, we use RGBN images to support a relighting step integrated in a sketch-based deformation method. We warp not only colors but also normals. Normal warping requires smooth warping fields. We use sketches to specify sparse warping samples and impose… Show more

While current image deformation methods are careful in making the new geometry seem right, little attention has been given to the photometric aspects. We introduce a deformation method that results in coherently illuminated objects. For this task, we use RGBN images to support a relighting step integrated in a sketch-based deformation method. We warp not only colors but also normals. Normal warping requires smooth warping fields. We use sketches to specify sparse warping samples and impose additional constraints for region of interest control. To satisfy these new constraints, we present a novel image warping method based on Hermite–Birkhoff interpolation with radial basis functions that results in a smooth warping field. We also use sketches to help the system identify both lighting conditions and material from single images. We present results with RGBN images from different sources, including photometric stereo, synthetic images, and photographs. Show less

We present techniques for rendering implicit surfaces in different pen-and-ink styles. The implicit models are rendered using point-based primitives to depict shape and tone using silhouettes with hidden-line attenuation, drawing directions, and stippling. We present sample renderings obtained for a variety of models. Furthermore, we describe simple and novel methods to control point placement and rendering style. Our approach is implemented using HRBF Implicits, a simple and compact… Show more

We present techniques for rendering implicit surfaces in different pen-and-ink styles. The implicit models are rendered using point-based primitives to depict shape and tone using silhouettes with hidden-line attenuation, drawing directions, and stippling. We present sample renderings obtained for a variety of models. Furthermore, we describe simple and novel methods to control point placement and rendering style. Our approach is implemented using HRBF Implicits, a simple and compact representation, that has three fundamental qualities: a small number of point-normal samples as input for surface reconstruction, good projection of points near the surface, and smoothness of the gradient field. These qualities of HRBF Implicits are used to generate a robust distribution of points to position the drawing primitives. Show less

In this work we present a family of methods designed to represent implicitly-defined hypersurfaces satisfying prescribed constraints. These methods arise rather naturally from a theoretical framework of generalized interpolation in function spaces induced by certain radial basis functions (RBFs). After the mathematical preliminaries, we introduce Hermite Radial Basis Functions (HRBF) Implicits as a representation for implicit surfaces appearing naturally from the special case of (first-order)… Show more

In this work we present a family of methods designed to represent implicitly-defined hypersurfaces satisfying prescribed constraints. These methods arise rather naturally from a theoretical framework of generalized interpolation in function spaces induced by certain radial basis functions (RBFs). After the mathematical preliminaries, we introduce Hermite Radial Basis Functions (HRBF) Implicits as a representation for implicit surfaces appearing naturally from the special case of (first-order) Hermite interpolation with RBFs. HRBF Implicits reconstruct an implicit function which interpolates or approximates scattered multivariate Hermite data (i.e. unstructured points and their corresponding normals) and its theory unifies a recently introduced class of surface reconstruction methods based on RBFs which incorporate normals directly in their problem formulation. This class has the advantage of not depending on manufactured offset-points to ensure existence of a non-trivial RBF interpolant. This framework not only allows us to show connections between the present method and others but also enables us to enhance the flexibility of this method by ensuring well-posedness of an interesting combined interpolation/regularisation approach. Following our presentation of HRBF Implicits, we present other formulations which relax the assumptions on the nature of the datasets. For instance, we begin by relaxing a coherence requirement on the input normals and present two different approaches to recover implicitly-defined hypersufaces from points and normal-directions, one which only solves a linear system and another based on an eigenvalue problem. After that, we show a formulation which does not require normals but still reconstructs a nontrivial implicit function by computing the “optimal” normals in a rather natural sense through the solution of another eigenvalue problem. Show less

The Hermite radial basis functions (HRBF) implicits reconstruct an implicit function which interpolates or approximates scattered multivariate Hermite data (i.e. unstructured points and their corresponding normals). Experiments suggest that HRBF implicits allow the reconstruction of surfaces rich in details and behave better than previous related methods under coarse and/or non-uniform samplings, even in the presence of close sheets. HRBF implicits theory unifies a recently introduced class of… Show more

The Hermite radial basis functions (HRBF) implicits reconstruct an implicit function which interpolates or approximates scattered multivariate Hermite data (i.e. unstructured points and their corresponding normals). Experiments suggest that HRBF implicits allow the reconstruction of surfaces rich in details and behave better than previous related methods under coarse and/or non-uniform samplings, even in the presence of close sheets. HRBF implicits theory unifies a recently introduced class of surface reconstruction methods based on radial basis functions (RBF), which incorporate normals directly in their problem formulation. Such class has the advantage of not depending on manufactured offset-points to ensure existence of a non-trivial implicit surface RBF interpolant. In fact, we show that HRBF implicits constitute a particular case of Hermite–Birkhoff interpolation with radial basis functions, whose main results we present here. This framework not only allows us to show connections between the present method and others but also enable us to enhance the flexibility of our method by ensuring well-posedness of an interesting combined interpolation/regularization approach. Show less

We present techniques for modeling Variational Hermite Radial Basis Function (VHRBF) Implicits using a set of sketch-based interface and modeling (SBIM) operators. VHRBF Implicits is a simple and compact representation well suited for SBIM. It provides quality reconstructions, preserving the intended shape from a coarse and non-uniform number of point-normal samples extracted directly from the input strokes. In addition, it has a number of desirable properties such as parameter-free modeling… Show more

We present techniques for modeling Variational Hermite Radial Basis Function (VHRBF) Implicits using a set of sketch-based interface and modeling (SBIM) operators. VHRBF Implicits is a simple and compact representation well suited for SBIM. It provides quality reconstructions, preserving the intended shape from a coarse and non-uniform number of point-normal samples extracted directly from the input strokes. In addition, it has a number of desirable properties such as parameter-free modeling, invariance under geometric similarities on the input strokes, suitable estimation of differential quantities, good behavior near close sheets, and both linear fitting and reproduction. Our approach uses these properties of VHRBF Implicits to quickly and robustly generate the overall shape of 3D models. We present examples of implicit models obtained from a set of SBIM language operators for contouring, cross-editing, kneading, oversketching and merging. Show less

In this paper, we present a 3D face photography system based on a facial expression training dataset, composed of both facial range images (3D geometry) and facial texture (2D photography). The proposed system allows one to obtain a 3D geometry representation of a given face provided as a 2D photography, which undergoes a series of transformations through the texture and geometry spaces estimated. In the training phase of the system, the facial landmarks are obtained by an active shape model… Show more

In this paper, we present a 3D face photography system based on a facial expression training dataset, composed of both facial range images (3D geometry) and facial texture (2D photography). The proposed system allows one to obtain a 3D geometry representation of a given face provided as a 2D photography, which undergoes a series of transformations through the texture and geometry spaces estimated. In the training phase of the system, the facial landmarks are obtained by an active shape model (ASM) extracted from the 2D gray-level photography. Principal components analysis (PCA) is then used to represent the face dataset, thus defining an orthonormal basis of texture and another of geometry. In the reconstruction phase, an input is given by a face image to which the ASM is matched. The extracted facial landmarks and the face image are fed to the PCA basis transform, and a 3D version of the 2D input image is built. Experimental tests using a new dataset of 70 facial expressions belonging to ten subjects as training set show rapid reconstructed 3D faces which maintain spatial coherence similar to the human perception, thus corroborating the efficiency and the applicability of the proposed system. Show less