{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/84869"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/84869","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing","abstract":"In this thesis, we establish theoretical guarantees for several dimension reduction algorithms developed for applications in compressive sensing and signal processing. In each instance, the input is a point or set of points in d-dimensional Euclidean space, and the goal is to find a linear function from Rd into Rk , where k << d, such that the resulting embedding of the input pointset into k-dimensional Euclidean space has various desirable properties. We focus on two classes of theoretical results: -- First, we examine linear embeddings of arbitrary pointsets with the aim of minimizing distortion. We present an exhaustive-search-based algorithm that yields a k-dimensional linear embedding with distortion at most ... is the smallest possible distortion over all orthonormal embeddings into k dimensions. This PTAS-like result transcends lower bounds for well-known embedding teclhniques such as the Johnson-Lindenstrauss transform. -- Next, motivated by compressive sensing of images, we examine linear embeddings of datasets containing points that are sparse in the pixel basis, with the goal of recoving a nearly-optimal sparse approximation to the original data. We present several algorithms that achieve strong recovery guarantees using the near-optimal bound of measurements, while also being highly \"local\" so that they can be implemented more easily in physical devices. We also present some impossibility results concerning the existence of such embeddings with stronger locality properties.","abstract_html":"In this thesis, we establish theoretical guarantees for several dimension reduction algorithms developed for applications in compressive sensing and signal processing. In each instance, the input is a point or set of points in d-dimensional Euclidean space, and the goal is to find a linear function from Rd into Rk , where k &lt;&lt; d, such that the resulting embedding of the input pointset into k-dimensional Euclidean space has various desirable properties. We focus on two classes of theoretical results: -- First, we examine linear embeddings of arbitrary pointsets with the aim of minimizing distortion. We present an exhaustive-search-based algorithm that yields a k-dimensional linear embedding with distortion at most ... is the smallest possible distortion over all orthonormal embeddings into k dimensions. This PTAS-like result transcends lower bounds for well-known embedding teclhniques such as the Johnson-Lindenstrauss transform. -- Next, motivated by compressive sensing of images, we examine linear embeddings of datasets containing points that are sparse in the pixel basis, with the goal of recoving a nearly-optimal sparse approximation to the original data. We present several algorithms that achieve strong recovery guarantees using the near-optimal bound of measurements, while also being highly &quot;local&quot; so that they can be implemented more easily in physical devices. We also present some impossibility results concerning the existence of such embeddings with stronger locality properties.","abstract_has_math":false,"creators":["Grant, Elyot"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Piotr Indyk."],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013","date_published":"2013","updated_at":"2026-07-22T22:21:48Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/84869","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Piotr Indyk."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Grant, Elyot"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-02-10T16:56:35Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-02-10T16:56:35Z"]},{"key":"dc:date.issued","label":"Date","values":["2013"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/84869"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 41-42)."]},{"key":"dc:description.abstract","label":"Abstract","values":["In this thesis, we establish theoretical guarantees for several dimension reduction algorithms developed for applications in compressive sensing and signal processing. In each instance, the input is a point or set of points in d-dimensional Euclidean space, and the goal is to find a linear function from Rd into Rk , where k << d, such that the resulting embedding of the input pointset into k-dimensional Euclidean space has various desirable properties. We focus on two classes of theoretical results: -- First, we examine linear embeddings of arbitrary pointsets with the aim of minimizing distortion. We present an exhaustive-search-based algorithm that yields a k-dimensional linear embedding with distortion at most ... is the smallest possible distortion over all orthonormal embeddings into k dimensions. This PTAS-like result transcends lower bounds for well-known embedding teclhniques such as the Johnson-Lindenstrauss transform. -- Next, motivated by compressive sensing of images, we examine linear embeddings of datasets containing points that are sparse in the pixel basis, with the goal of recoving a nearly-optimal sparse approximation to the original data. We present several algorithms that achieve strong recovery guarantees using the near-optimal bound of measurements, while also being highly \"local\" so that they can be implemented more easily in physical devices. We also present some impossibility results concerning the existence of such embeddings with stronger locality properties."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:title","label":"Title","values":["Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing"]}]}],"canonical_facts":{"dc:contributor.advisor":["Piotr Indyk."],"dc:contributor.department":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science."],"dc:creator":["Grant, Elyot"],"dc:date.accessioned":["2014-02-10T16:56:35Z"],"dc:date.available":["2014-02-10T16:56:35Z"],"dc:date.issued":["2013"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2013.","Cataloged from PDF version of thesis.","Includes bibliographical references (pages 41-42)."],"dc:description.abstract":["In this thesis, we establish theoretical guarantees for several dimension reduction algorithms developed for applications in compressive sensing and signal processing. In each instance, the input is a point or set of points in d-dimensional Euclidean space, and the goal is to find a linear function from Rd into Rk , where k << d, such that the resulting embedding of the input pointset into k-dimensional Euclidean space has various desirable properties. We focus on two classes of theoretical results: -- First, we examine linear embeddings of arbitrary pointsets with the aim of minimizing distortion. We present an exhaustive-search-based algorithm that yields a k-dimensional linear embedding with distortion at most ... is the smallest possible distortion over all orthonormal embeddings into k dimensions. This PTAS-like result transcends lower bounds for well-known embedding teclhniques such as the Johnson-Lindenstrauss transform. -- Next, motivated by compressive sensing of images, we examine linear embeddings of datasets containing points that are sparse in the pixel basis, with the goal of recoving a nearly-optimal sparse approximation to the original data. We present several algorithms that achieve strong recovery guarantees using the near-optimal bound of measurements, while also being highly \"local\" so that they can be implemented more easily in physical devices. We also present some impossibility results concerning the existence of such embeddings with stronger locality properties."],"dc:description.degree":["S.M."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/84869"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Dimension reduction algorithms for near-optimal low-dimensional embeddings and compressive sensing"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:48Z"}