Deep feature spaces have the capacity to encode complex transformations of their input data. However, understanding the relative feature-space relationship between two transformed encoded images is difficult. For instance, what is the relative feature space relationship between two rotated images? What is decoded when we interpolate in feature space? Ideally, we want to disentangle confounding factors, such as pose, appearance, and illumination, from object identity. Disentangling these is difficult because they interact in very nonlinear ways. We propose a simple method to construct a deep feature space, with explicitly disentangled representations of several known transformations. A person or algorithm can then manipulate the disentangled representation, for example, to re-render an image with explicit control over parameterized degrees of freedom. The feature space is constructed using a transforming encoder-decoder network with a custom feature transform layer, acting on the hidden representations. We demonstrate the advantages of explicit disentangling on a variety of datasets and transformations, and as an aid for traditional tasks, such as classification.
A function @math is @cite_4 under a set of transformations @math if for any transformation @math of the input, we can associate a transformation @math of the output such that for all @math . Transformations @math and @math represent the same underlying transformation but in different spaces, denoted @math .
@cite_4
2073082201
Let @math denote a set of polynomials with complex coefficients. Let @math denote any set of sample points . For any @math , the discrete polynomial transform of @math (with respect to @math and @math ) is defined as the collection of sums, @math , where @math for some associated weight function @math . These sorts of transforms find important applications in areas such as medical imaging and signal processing. In this paper, we present fast algorithms for computing discrete orthogonal polynomial transforms. For a system of @math orthogonal polynomials of degree at most @math , we give an @math algorithm for computing a discrete polynomial transform at an arbitrary set of points instead of the @math operations required by direct evaluation. Our algorithm depends only on the fact that orthogonal polynomial sets satisfy a three-term recurrence and thus it may be applied to any such set of discretely sampled functions. In particular, sampled orthogonal polynomials generate the vector space of functions on a distance transitive graph. As a direct application of our work, we are able to give a fast algorithm for computing subspace decompositions of this vector space which respect the action of the symmetry group of such a graph. This has direct applications to treating computational bottlenecks in the spectral analysis of data on distance transitive graphs, and we discuss this in some detail. We introduce a complete parameterization of the family of two-dimensional steerable wavelets that are polar-separable in the Fourier domain under the constraint of self-reversibility. These wavelets are constructed by multiorder generalized Riesz transformation of a primary isotropic bandpass pyramid. The backbone of the transform (pyramid) is characterized by a radial frequency profile function @math , while the directional wavelet components at each scale are encoded by an @math shaping matrix @math , where @math is the number of wavelet channels and @math the order of the Riesz transform. We provide general conditions on @math and @math for the underlying wavelet system to form a tight frame of @math (with a redundancy factor @math ). The proposed framework ensures that the wavelets are steerable and provides new degrees of freedom (shaping matrix @math ) that can be exploited for designing specific wavelet systems. It encompasses many known transforms as part... Finite convex geometries are combinatorial structures. It follows from a recent result of M. Richter and L.G. Rogers that there is an infinite set @math of planar convex polygons such that @math with respect to geometric convex hulls is a locally convex geometry and every finite convex geometry can be represented by restricting the structure of @math to a finite subset in a natural way. An @math is a differentiable convex simple closed curve @math in the plane having an inscribed circle of radius @math and a circumscribed circle of radius @math such that the ratio @math is at least @math . Motivated by Richter and Rogers' result, we construct a set @math such that (1) @math contains all points of the plane as degenerate singleton circles and all of its non-singleton members are differentiable convex simple closed planar curves; (2) @math with respect to the geometric convex hull operator is a locally convex geometry; (3) as opposed to @math , @math is closed with respect to non-degenerate affine transformations; and (4) for every (small) positive @math and for every finite convex geometry, there are continuum many pairwise affine-disjoint finite subsets @math of @math such that each @math consists of almost-circles of accuracy @math and the convex geometry in question is represented by restricting the convex hull operator to @math . The affine-disjointness of @math and @math means that, in addition to @math , even @math is disjoint from @math for every non-degenerate affine transformation @math . Consider a binary maximum distance separate (MDS) array code composed of an @math array of bits with @math information columns and @math parity columns, such that any @math out of @math columns suffice to reconstruct the @math information columns. Our goal is to provide optimal repair access for binary MDS array codes, meaning that the bandwidth triggered to repair any single failed information or parity column is minimized. In this paper, we propose a generic transformation framework for binary MDS array codes, using EVENODD codes as a motivating example, to support optimal repair access for @math , where @math denotes the number of non-failed columns that are connected for repair. In addition, we show that the efficient decoding property of the original EVENODD codes is maintained after transformation. Furthermore, we show how our transformation framework applies to general binary MDS array codes and enables them to support optimal repair access. We consider the problem of estimating a deterministic finite alphabet vector @math from underdetermined measurements @math , where @math is a given (random) @math matrix. Two new convex optimization methods are introduced for the recovery of finite alphabet signals via @math -norm minimization. The first method is based on regularization. In the second approach, the problem is formulated as the recovery of sparse signals after a suitable sparse transform. The regularization-based method is less complex than the transform-based one. When the alphabet size @math equals 2 and @math grows proportionally, the conditions under which the signal will be recovered with high probability are the same for the two methods. When @math , the behavior of the transform-based method is established. Experimental results support this theoretical result and show that the transform method outperforms the regularization-based one. Traditional GANs use a deterministic generator function (typically a neural network) to transform a random noise input @math to a sample @math that the discriminator seeks to distinguish. We propose a new GAN called Bayesian Conditional Generative Adversarial Networks (BC-GANs) that use a random generator function to transform a deterministic input @math to a sample @math . Our BC-GANs extend traditional GANs to a Bayesian framework, and naturally handle unsupervised learning, supervised learning, and semi-supervised learning problems. Experiments show that the proposed BC-GANs outperforms the state-of-the-arts. This paper proves that an "old dog", namely -- the classical Johnson-Lindenstrauss transform, "performs new tricks" -- it gives a novel way of preserving differential privacy. We show that if we take two databases, @math and @math , such that (i) @math is a rank-1 matrix of bounded norm and (ii) all singular values of @math and @math are sufficiently large, then multiplying either @math or @math with a vector of iid normal Gaussians yields two statistically close distributions in the sense of differential privacy. Furthermore, a small, deterministic and alteration of the input is enough to assert that all singular values of @math are large. We apply the Johnson-Lindenstrauss transform to the task of approximating cut-queries: the number of edges crossing a @math -cut in a graph. We show that the JL transform allows us to that preserves edge differential privacy (where two graphs are neighbors if they differ on a single edge) while adding only @math random noise to any given query (w.h.p). Comparing the additive noise of our algorithm to existing algorithms for answering cut-queries in a differentially private manner, we outperform all others on small cuts ( @math ). We also apply our technique to the task of estimating the variance of a given matrix in any given direction. The JL transform allows us to that preserves differential privacy w.r.t bounded changes (each row in the matrix can change by at most a norm-1 vector) while adding random noise of magnitude independent of the size of the matrix (w.h.p). In contrast, existing algorithms introduce an error which depends on the matrix dimensions. Let us consider the differential equation @math with an @math from @math to @math and suppose that there exists a transformation @math from @math to @math ( @math ) such that @math obeys a differential equation @math with some function @math ; then the first equation is said to be lumpable to the second by @math . Here mainly the case is investigated when the original differential equation has been induced by a complex chemical reaction. We provided a series of necessary and sufficient conditions for the existence of such functions @math and @math ; some of them are formulated in terms of @math and @math only. Beyond these conditions our main concern here is how lumping changes those properties of the solutions which are either interesting from the point of view of the qualitative theory of differential equations or from the point ... We introduce a new low-distortion embedding of @math into @math ( @math ) called the fast Johnson-Lindenstrauss transform (FJLT). The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the “Heisenberg principle” of the Fourier transform, i.e., its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in @math and @math . We consider the case of approximate nearest neighbors in @math . We provide a faster algorithm using classical projections, which we then speed up further by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube. We propose a generic transformation that can convert any nonbinary @math maximum distance separable (MDS) code into another @math MDS code over the same field such that: 1) some arbitrarily chosen @math nodes have the optimal repair bandwidth and the optimal rebuilding access; 2) for the remaining @math nodes, the normalized repair bandwidth and the normalized rebuilding access (over the file size) are preserved; and 3) the sub-packetization level is increased only by a factor of @math . Two immediate applications of this generic transformation are then presented. The first application is that we can transform any nonbinary MDS code with the optimal repair bandwidth or the optimal rebuilding access for the systematic nodes only, into a new MDS code which possesses the corresponding repair optimality for all nodes. The second application is that by applying the transformation multiple times, any nonbinary @math scalar MDS code can be converted into an @math MDS code with the optimal repair bandwidth and the optimal rebuilding access for all nodes, or only a subset of nodes, whose sub-packetization level is also optimal. We present a 6-approximation algorithm for the minimum-cost @math -node connected spanning subgraph problem, assuming that the number of nodes is at least @math . We apply a combinatorial preprocessing, based on the Frank--Tardos algorithm for @math -outconnectivity, to transform any input into an instance such that the iterative rounding method gives a 2-approximation guarantee. This is the first constant factor approximation algorithm even in the asymptotic setting of the problem, that is, the restriction to instances where the number of nodes is lower bounded by a function of @math . Given a set @math with @math elements and a family @math of subsets, we show how to partition @math into @math such subsets in @math time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in @math time for several well-studied partition problems including domatic number, chromatic number, maximum @math -cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time @math if membership in @math can be decided in polynomial time. We solve chromatic number in @math time and domatic number in @math time. Finally, we present a family of polynomial space approximation algorithms that find a number between @math and @math in time @math . A group of algorithms is presented generalizing the fast Fourier transform to the case of noninteger frequencies and nonequispaced nodes on the interval @math . The schemes of this paper are based on a combination of certain analytical considerations with the classical fast Fourier transform and generalize both the forward and backward FFTs. Each of the algorithms requires @math arithmetic operations, where @math is the precision of computations and N is the number of nodes. The efficiency of the approach is illustrated by several numerical examples. Inspired by the early visual system of many mammalians we consider the construction of-and reconstruction from- an orientation score @math as a local orientation representation of an image, @math . The mapping @math is a wavelet transform @math corresponding to a reducible representation of the Euclidean motion group onto @math and oriented wavelet @math . This wavelet transform is a special case of a recently developed generalization of the standard wavelet theory and has the practical advantage over the usual wavelet approaches in image analysis (constructed by irreducible representations of the similitude group) that it allows a stable reconstruction from one (single scale) orientation score. Since our wavelet transform is a unitary mapping with stable inverse, we directly relate operations on orientation scores to operations on images in a robust manner. Furthermore, by geometrical examination of the Euclidean motion group @math , which is the domain of our orientation scores, we deduce that an operator ? on orientation scores must be left invariant to ensure that the corresponding operator @math on images is Euclidean invariant. As an example we consider all linear second order left invariant evolutions on orientation scores corresponding to stochastic processes on G. As an application we detect elongated structures in (medical) images and automatically close the gaps between them. Finally, we consider robust orientation estimates by means of channel representations, where we combine robust orientation estimation and learning of wavelets resulting in an auto-associative processing of orientation features. Here linear averaging of the channel representation is equivalent to robust orientation estimation and an adaptation of the wavelet to the statistics of the considered image class leads to an auto-associative behavior of the system. Consider the problem of recovering a measure @math supported on a lattice of span @math , when measurements are only available concerning the Fourier Transform @math at frequencies @math . If @math is much smaller than the Nyquist frequency @math and the measurements are noisy, then, in general, stable recovery of @math is impossible. In this paper it is shown that if, in addition, we know that the measure @math satisfies certain sparsity constraints, then stable recovery is possible. Say that a set has Rayleigh index less than or equal to R if in any interval of length @math there are at most R elements. Indeed, if the (unknown) support of @math is known, a priori, to have Rayleigh index at most R, then stable recovery is possible with a stability coefficient that grows at most like @math as @math . This result validates certain practical efforts, in spectroscopy, seismic prospecting, and astrono... Interpolators---estimators that achieve zero training error---have attracted growing attention in machine learning, mainly because state-of-the art neural networks appear to be models of this type. In this paper, we study minimum @math norm ( ridgeless') interpolation in high-dimensional least squares regression. We consider two different models for the feature distribution: a linear model, where the feature vectors @math are obtained by applying a linear transform to a vector of i.i.d. entries, @math (with @math ); and a nonlinear model, where the feature vectors are obtained by passing the input through a random one-layer neural network, @math (with @math , @math a matrix of i.i.d. entries, and @math an activation function acting componentwise on @math ). We recover---in a precise quantitative way---several phenomena that have been observed in large-scale neural networks and kernel machines, including the double descent' behavior of the prediction risk, and the potential benefits of overparametrization. This article offers a simplified approach to the distribution theory of randomly weighted averages or @math -means @math , for a sequence of i.i.d.random variables @math , and independent random weights @math with @math and @math . The collection of distributions of @math , indexed by distributions of @math , is shown to encode Kingman's partition structure derived from @math . For instance, if @math has Bernoulli @math distribution on @math , the @math th moment of @math is a polynomial function of @math which equals the probability generating function of the number @math of distinct values in a sample of size @math from @math : @math . This elementary identity illustrates a general moment formula for @math -means in terms of the partition structure associated with random samples from @math , first developed by Diaconis and Kemperman (1996) and Kerov (1998) in terms of random permutations. As shown by Tsilevich (1997) if the partition probabilities factorize in a way characteristic of the generalized Ewens sampling formula with two parameters @math , found by Pitman (1992), then the moment formula yields the Cauchy-Stieltjes transform of an @math mean. The analysis of these random means includes the characterization of @math -means, known as Dirichlet means, due to Von Neumann (1941), Watson (1956) and Cifarelli and Regazzini (1990) and generalizations of L 'evy's arcsine law for the time spent positive by a Brownian motion, due to Darling (1949) Lamperti (1958) and Barlow, Pitman and Yor (1989). The field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array (CSA) by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing. We report the following advances in string indexing and analysis. We show that the BWT of a string @math can be built in deterministic @math time using just @math bits of space, where @math . Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of @math . Many fundamental string analysis problems can be mapped to such enumeration, and can thus be solved in deterministic @math time and in @math bits of space from the input string. We also show how to build many of the existing indexes based on the BWT, such as the CSA, the compressed suffix tree (CST), and the bidirectional BWT index, in randomized @math time and in @math bits of space. The previously fastest construction algorithms for BWT, CSA and CST, which used @math bits of space, took @math time for the first two structures, and @math time for the third, where @math is any positive constant. Contrary to the state of the art, our bidirectional BWT index supports every operation in constant time per element in its output. For every fixed constant @math , we design an algorithm for computing the @math -sparse Walsh-Hadamard transform of an @math -dimensional vector @math in time @math . Specifically, the algorithm is given query access to @math and computes a @math -sparse @math satisfying @math , for an absolute constant @math , where @math is the transform of @math and @math is its best @math -sparse approximation. Our algorithm is fully deterministic and only uses non-adaptive queries to @math (i.e., all queries are determined and performed in parallel when the algorithm starts). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan, JACM 2009). Moreover, we design a deterministic and non-adaptive @math compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time @math (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk, Karloff, Strauss (Allerton 2008). Our methods use linear lossless condensers in a black box fashion; therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to @math reconstruction time with a reduced exponent in the poly-logarithmic factor, and eliminating the extra parameter @math ). Finally, by allowing the algorithm to use randomness, while still using non-adaptive queries, the running time of the algorithm can be improved to @math . A numerically stable and fairly fast scheme is described to compute the unitary matrices U and V which transform a given matrix A into a diagonal form @math , thus exhibiting A’s singular values on @math ’s diagonal. The scheme first transforms A to a bidiagonal matrix J, then diagonalizes J. The scheme described here is complicated but does not suffer from the computational difficulties which occasionally afflict some previously known methods. Some applications are mentioned, in particular the use of the pseudo-inverse @math to solve least squares problems in a way which dampens spurious oscillation and cancellation.