Many computational problems involve massive data. A reasonable solution to those problems should be able to store and process the data in a effective manner. In this thesis, we study sparse representation of data streams and metric spaces, which allows for fast and private computation of heavy hitters from distributed streams, and approximate distance queries between points in a metric space. Specifically, we consider application scenarios where an untrusted aggregator wishes to continually monitor the heavy-hitters across a set of distributed streams. Since each stream can contain sensitive data, such as the purchase history of customers, we wish to guarantee the privacy of each stream, while allowing the untrusted aggregator to accurately detect the heavy hitters and their approximate frequencies. Our protocols are scalable in settings where the volume of streaming data is large, since we guarantee low memory usage and processing overhead by each data source, and low communication overhead between the data sources and the aggregator. We also study fault-tolerant spanners in doubling metrics. A subgraph H for a metric space X is called a k-vertex-fault-tolerant t-spanner ((k; t)-VFTS or simply k-VFTS), if for any subset S _ X with |Sj|≤k, it holds that dHnS(x; y) ≤ t ∙d(x; y), for any pair of x, y ∈ X \ S. For any doubling metric, we give a basic construction of k-VFTS with stretch arbitrarily close to 1 that has optimal O(kn) edges. We also consider bounded hop-diameter, which is studied in the context of fault-tolerance for the first time even for Euclidean spanners. We provide a construction of k-VFTS with bounded hop-diameter: for m ≥2n, we can reduce the hop-diameter of the above k-VFTS to O(α(m; n)) by adding O(km) edges, where α is a functional inverse of the Ackermann's function. In addition, we construct a fault-tolerant single-sink spanner with bounded maximum degree, and use it to reduce the maximum degree of our basic k-VFTS. As a result, we get a k-VFTS with O(k^2n) edges and maximum degree O(k^2). / published_or_final_version / Computer Science / Master / Master of Philosophy

As the social networking applications become popular and have attracted more and more attention, it becomes possible (or easier) to mine information networks of a large group of people, for instance the spread of viruses, products and innovations. Researchers are also benefited from these sources, as they help to study further about the human behaviors in a social networking environment. In this thesis, we study how the opinions cascade via social links and also the sparse representation of large data sets caused by the fast growing information networks. Consider an instance of advertising products on an information network, where the objective for an advertiser is to choose a set of initially active nodes, subject to some budget constraints such that the expected number of active nodes over time is maximized. In this work, the non-progressive case where active nodes could become inactive in subsequent time steps, was considered. This setting is interesting, for people have no reason to keep using a product forever, especially when a majority of his neighbors have given it up. Another setting is the users' susceptibilities to the new behavior won't change once they are chosen initially. This is di_erent from the previous works, and we think it is also interesting. Our main result is that with a specified budget, an advertiser can achieve 1/2 -approximation on maximizing the number of active nodes over a certain period of time, and (1 - 1/e)-approximation in expectation with a randomized algorithm. In our model, users' opinions are updated according to a weighted averaging scheme, which usually leads to the consensus. When this happens, the expected influence over a long time period is dominated by the consensus value. Hence, it is interesting to study when and how the consensus will be achieved. We study the convergence time required to achieve consensus. In particular, we considered the case when the underlying network is dynamic, and gave conclusions for different averaging models. Both our analysis and experiments show that dynamic networks exhibit fast convergence behavior, even under very mild connectivity assumptions. In this work, we also studied how to maintain the pairwise distances for a large group of users, when the distances form a doubling metric space. Motivated by Elkin and Solomon's construction of spanners for doubling metrics that has constant maximum degree, hop-diameter O(log n) and lightness O(log n) (i.e., weight O(log n) ． w(MST)), we offer a simple alternative construction that is very intuitive and is based on the standard technique of net tree with cross edges. Indeed, our approach can be readily applied to our previous construction of k-fault tolerant spanners (ICALP 2012) to achieve k-fault tolerance, maximum degree O(K^2), hop-diameter O(log n) and lightness O(K^3 log n). / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

The minimum degree algorithm is known as an effective scheme for identifying a fill reduced ordering for symmetric, positive definite, sparse linear systems, to be solved using a Cholesky factorization. Although the original algorithm has been enhanced to improve the efficiency of its implementation, ties between minimum degree elimination candidates are still arbitrarily broken. For many systems, the fill levels of orderings produced by the minimum degree algorithm are very sensitive to the precise manner in which these ties are resolved. This thesis introduces several tiebreaking enhancements of the minimum degree algorithm. Emphasis is placed upon a tiebreaking strategy based upon the deficiency of minium degree elimination candidates, and which can consistently identify low fill orderings for a wide spectrum of test problems. All tiebreaking strategies are fully integrated into implementations of the minimum degree algorithm based upon a quotient graph model, including indistinguishable sets represented by uneliminated supernodes. The resulting programs are tested on a wide variety of sparse systems in order to investigate the performance of the algorithm enhanced by the tiebreaking strategies and the quality of the orderings they produce. / Science, Faculty of / Computer Science, Department of / Graduate

M.Phil. (Energy Studies) / Nodal diffusion methods are often used to calculate the distribution of neutrons in a nuclear reactor core. They require few-group homogenized neutron cross sections for every heterogeneous sub-region of the core. The homogenized cross sections are pre-calculated at various reactor states and represented in a way that facilitates the reconstruction of cross sections at other possible states. In this study a number of such representations were built for the homogenized cross sections of a MOX (mixed oxide) fuel assembly via hierarchical Lagrange interpolation on Clenshaw-Curtis sparse grids. These cross sections were represented as a function of various thermal hydraulic and material composition parameters of a pressurized water reactor core (i.e. burnup, soluble boron concentration, fuel temperature, moderator temperature and moderator density), which are generally referred to as state parameters. Representations were produced for the homogenized cross sections of a number of individual isotopes, as well as the e ective (lumped) cross section of all the materials in the assembly. This was done for both two and six energy groups. Additionally, two sets of state parameter intervals were considered for each of the group structures. The first set of intervals was chosen to correspond to conditions that may be encountered during day-to-day reactor operations. The second set of intervals was chosen to be applicable to the simulation of accident scenarios and therefore have wider ranges for fuel temperature, moderator temperature and moderator density.

Wu, King Keung. / "August 2011." / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 119-126). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.v / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview of Face Alignment Algorithms --- p.1 / Chapter 1.1.1 --- Objectives --- p.1 / Chapter 1.1.2 --- Motivation: Photo-realistic Talking Head --- p.2 / Chapter 1.1.3 --- Existing methods --- p.5 / Chapter 1.2 --- Contributions --- p.8 / Chapter 1.3 --- Outline of the Thesis --- p.11 / Chapter 2 --- Sparse Signal Representation --- p.13 / Chapter 2.1 --- Introduction --- p.13 / Chapter 2.2 --- Problem Formulation --- p.15 / Chapter 2.2.1 --- l0-nonn minimization --- p.15 / Chapter 2.2.2 --- Uniqueness --- p.16 / Chapter 2.3 --- Basis Pursuit --- p.18 / Chapter 2.3.1 --- From l0-norm to l1-norm --- p.19 / Chapter 2.3.2 --- l0-l1 Equivalence --- p.20 / Chapter 2.4 --- l1-Regularized Least Squares --- p.21 / Chapter 2.4.1 --- Noisy case --- p.22 / Chapter 2.4.2 --- Over-determined systems of linear equations --- p.22 / Chapter 2.5 --- Summary --- p.24 / Chapter 3 --- Sparse Corruptions and Principal Component Pursuit --- p.25 / Chapter 3.1 --- Introduction --- p.25 / Chapter 3.2 --- Sparse Corruptions --- p.26 / Chapter 3.2.1 --- Sparse Corruptions and l1-Error --- p.26 / Chapter 3.2.2 --- l1-Error and Least Absolute Deviations --- p.28 / Chapter 3.2.3 --- l1-Regularized l1-Error --- p.29 / Chapter 3.3 --- Robust Principal Component Analysis (RPCA) and Principal Component Pursuit --- p.31 / Chapter 3.3.1 --- Principal Component Analysis (PCA) and RPCA --- p.31 / Chapter 3.3.2 --- Principal Component Pursuit --- p.33 / Chapter 3.4 --- Experiments of Sparse and Low-rank Approach on Surveillance Video --- p.34 / Chapter 3.4.1 --- Least Squares --- p.35 / Chapter 3.4.2 --- l1-Regularized Least Squares --- p.35 / Chapter 3.4.3 --- l1-Error --- p.36 / Chapter 3.4.4 --- l1-Regularized l1-Error --- p.36 / Chapter 3.5 --- Summary --- p.37 / Chapter 4 --- Split Bregman Algorithm for l1-Problem --- p.45 / Chapter 4.1 --- Introduction --- p.45 / Chapter 4.2 --- Bregman Distance --- p.46 / Chapter 4.3 --- Bregman Iteration for Constrained Optimization --- p.47 / Chapter 4.4 --- Split Bregman Iteration for l1-Regularized Problem --- p.50 / Chapter 4.4.1 --- Formulation --- p.51 / Chapter 4.4.2 --- Advantages of Split Bregman Iteration . . --- p.52 / Chapter 4.5 --- Fast l1 Algorithms --- p.54 / Chapter 4.5.1 --- l1-Regularized Least Squares --- p.54 / Chapter 4.5.2 --- l1-Error --- p.55 / Chapter 4.5.3 --- l1-Regularized l1-Error --- p.57 / Chapter 4.6 --- Summary --- p.58 / Chapter 5 --- Face Alignment Using Sparse and Low-rank Decomposition --- p.61 / Chapter 5.1 --- Robust Alignment by Sparse and Low-rank Decomposition for Linearly Correlated Images (RASL) --- p.61 / Chapter 5.2 --- Problem Formulation --- p.62 / Chapter 5.2.1 --- Theory --- p.62 / Chapter 5.2.2 --- Algorithm --- p.64 / Chapter 5.3 --- Direct Extension of RASL: Multi-RASL --- p.66 / Chapter 5.3.1 --- Formulation --- p.66 / Chapter 5.3.2 --- Algorithm --- p.67 / Chapter 5.4 --- Matlab Implementation Details --- p.68 / Chapter 5.4.1 --- Preprocessing --- p.70 / Chapter 5.4.2 --- Transformation --- p.73 / Chapter 5.4.3 --- Jacobian Ji --- p.74 / Chapter 5.5 --- Experiments --- p.75 / Chapter 5.5.1 --- Qualitative Evaluations Using Small Dataset --- p.76 / Chapter 5.5.2 --- Large Dataset Test --- p.81 / Chapter 5.5.3 --- Conclusion --- p.85 / Chapter 5.6 --- Sensitivity analysis on selection of references --- p.87 / Chapter 5.6.1 --- References from consecutive frames --- p.88 / Chapter 5.6.2 --- References from RASL-aligned images --- p.91 / Chapter 5.7 --- Summary --- p.92 / Chapter 6 --- Extension of RASL for video: One-by-One Approach --- p.96 / Chapter 6.1 --- One-by-One Approach --- p.96 / Chapter 6.1.1 --- Motivation --- p.97 / Chapter 6.1.2 --- Algorithm --- p.97 / Chapter 6.2 --- Choices of Optimization --- p.101 / Chapter 6.2.1 --- l1-Regularized Least Squares --- p.101 / Chapter 6.2.2 --- l1-Error --- p.102 / Chapter 6.2.3 --- l1-Regularized l1-Error --- p.103 / Chapter 6.3 --- Experiments --- p.104 / Chapter 6.3.1 --- Evaluation for Different l1 Algorithms --- p.104 / Chapter 6.3.2 --- Conclusion --- p.108 / Chapter 6.4 --- Exploiting Property of Video --- p.109 / Chapter 6.5 --- Summary --- p.110 / Chapter 7 --- Conclusion and Future Work --- p.112 / Chapter A --- Appendix --- p.117 / Bibliography --- p.119

Thesis (M.Sc.)--Memorial University of Newfoundland, 1999. / Bibliography: leaves 64-68.

Thesis (M.S.)--University of Florida, 2005. / Title from title page of source document. Document formatted into pages; contains 79 pages. Includes vita. Includes bibliographical references.

Thesis (M.S.)--Oregon Graduate Center, 1987.

Thesis (M.S. in Modeling, Virtual Environment, and Simulation (MOVES))--Naval Postgraduate School, March 2007. / Thesis Advisor(s): Christian Darken. "March 2007." Includes bibliographical references (p. 115). Also available in print.

<p>This thesis is focused on determinantal rings in 2 different contexts. In Chapter 3 the homological properties of powers of determinantal ideals are studied. In particular the focus is on local cohomology of determinantal thickenings and we explicitly describe the $R$-module structure of some of these local cohomology modules. In Chapter 4 we introduce \textit{generalized diagonal} matrices, a class of sparse matrices which contain diagonal and upper triangular matrices. We study the ideals of minors of such matrices and describe their properties such as height, multiplicity, and Cohen-Macaulayness. </p>