3 resultados para block model

em CaltechTHESIS


Relevância:

60.00% 60.00%

Publicador:

Resumo:

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:

  • For a given number of measurements, can we reliably estimate the true signal?
  • If so, how good is the reconstruction as a function of the model parameters?

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.

Relevância:

30.00% 30.00%

Publicador:

Resumo:

We investigate the 2d O(3) model with the standard action by Monte Carlo simulation at couplings β up to 2.05. We measure the energy density, mass gap and susceptibility of the model, and gather high statistics on lattices of size L ≤ 1024 using the Floating Point Systems T-series vector hypercube and the Thinking Machines Corp.'s Connection Machine 2. Asymptotic scaling does not appear to set in for this action, even at β = 2.10, where the correlation length is 420. We observe a 20% difference between our estimate m/Λ^─_(Ms) = 3.52(6) at this β and the recent exact analytical result . We use the overrelaxation algorithm interleaved with Metropolis updates and show that decorrelation time scales with the correlation length and the number of overrelaxation steps per sweep. We determine its effective dynamical critical exponent to be z' = 1.079(10); thus critical slowing down is reduced significantly for this local algorithm that is vectorizable and parallelizable.

We also use the cluster Monte Carlo algorithms, which are non-local Monte Carlo update schemes which can greatly increase the efficiency of computer simulations of spin models. The major computational task in these algorithms is connected component labeling, to identify clusters of connected sites on a lattice. We have devised some new SIMD component labeling algorithms, and implemented them on the Connection Machine. We investigate their performance when applied to the cluster update of the two dimensional Ising spin model.

Finally we use a Monte Carlo Renormalization Group method to directly measure the couplings of block Hamiltonians at different blocking levels. For the usual averaging block transformation we confirm the renormalized trajectory (RT) observed by Okawa. For another improved probabilistic block transformation we find the RT, showing that it is much closer to the Standard Action. We then use this block transformation to obtain the discrete β-function of the model which we compare to the perturbative result. We do not see convergence, except when using a rescaled coupling β_E to effectively resum the series. For the latter case we see agreement for m/ Λ^─_(Ms) at , β = 2.14, 2.26, 2.38 and 2.50. To three loops m/Λ^─_(Ms) = 3.047(35) at β = 2.50, which is very close to the exact value m/ Λ^─_(Ms) = 2.943. Our last point at β = 2.62 disagrees with this estimate however.

Relevância:

30.00% 30.00%

Publicador:

Resumo:

A general solution is presented for water waves generated by an arbitrary movement of the bed (in space and time) in a two-dimensional fluid domain with a uniform depth. The integral solution which is developed is based on a linearized approximation to the complete (nonlinear) set of governing equations. The general solution is evaluated for the specific case of a uniform upthrust or downthrow of a block section of the bed; two time-displacement histories of the bed movement are considered.

An integral solution (based on a linear theory) is also developed for a three-dimensional fluid domain of uniform depth for a class of bed movements which are axially symmetric. The integral solution is evaluated for the specific case of a block upthrust or downthrow of a section of the bed, circular in planform, with a time-displacement history identical to one of the motions used in the two-dimensional model.

Since the linear solutions are developed from a linearized approximation of the complete nonlinear description of wave behavior, the applicability of these solutions is investigated. Two types of non-linear effects are found which limit the applicability of the linear theory: (1) large nonlinear effects which occur in the region of generation during the bed movement, and (2) the gradual growth of nonlinear effects during wave propagation.

A model of wave behavior, which includes, in an approximate manner, both linear and nonlinear effects is presented for computing wave profiles after the linear theory has become invalid due to the growth of nonlinearities during wave propagation.

An experimental program has been conducted to confirm both the linear model for the two-dimensional fluid domain and the strategy suggested for determining wave profiles during propagation after the linear theory becomes invalid. The effect of a more general time-displacement history of the moving bed than those employed in the theoretical models is also investigated experimentally.

The linear theory is found to accurately approximate the wave behavior in the region of generation whenever the total displacement of the bed is much less than the water depth. Curves are developed and confirmed by the experiments which predict gross features of the lead wave propagating from the region of generation once the values of certain nondimensional parameters (which characterize the generation process) are known. For example, the maximum amplitude of the lead wave propagating from the region of generation has been found to never exceed approximately one-half of the total bed displacement. The gross features of the tsunami resulting from the Alaskan earthquake of 27 March 1964 can be estimated from the results of this study.