Exact Recovery of Sparse Signals Using Orthogonal Matching Pursuit: How Many Iterations Do We Need?

Name: Work Video:
Duration: 3 min 30 s
Jian Wang; Byonghyo Shim
{'id': 'https://openalex.org/W1854242841', 'doi': 'https://doi.org/10.1109/tsp.2016.2568162', 'title': 'Exact Recovery of Sparse Signals Using Orthogonal Matching Pursuit: How Many Iterations Do We Need?', 'display_name': 'Exact Recovery of Sparse Signals Using Orthogonal Matching Pursuit: How Many Iterations Do We Need?', 'publication_year': 2016, 'publication_date': '2016-05-12', 'ids': {'openalex': 'https://openalex.org/W1854242841', 'doi': 'https://doi.org/10.1109/tsp.2016.2568162', 'mag': '1854242841'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/tsp.2016.2568162', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S168680287', 'display_name': 'IEEE Transactions on Signal Processing', 'issn_l': '1053-587X', 'issn': ['1053-587X', '1941-0476'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319808', 'host_organization_name': 'Institute of Electrical and Electronics Engineers', 'host_organization_lineage': ['https://openalex.org/P4310319808'], 'host_organization_lineage_names': ['Institute of Electrical and Electronics Engineers'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5100370463', 'display_name': 'Jian Wang', 'orcid': 'https://orcid.org/0000-0002-5421-5678'}, 'institutions': [{'id': 'https://openalex.org/I200845125', 'display_name': 'Nanjing University of Information Science and Technology', 'ror': 'https://ror.org/02y0rxk19', 'country_code': 'CN', 'type': 'education', 'lineage': ['https://openalex.org/I200845125']}, {'id': 'https://openalex.org/I139264467', 'display_name': 'Seoul National University', 'ror': 'https://ror.org/04h9pn542', 'country_code': 'KR', 'type': 'education', 'lineage': ['https://openalex.org/I139264467']}], 'countries': ['CN', 'KR'], 'is_corresponding': False, 'raw_author_name': 'Jian Wang', 'raw_affiliation_strings': ['Department of Electrical and Computer Engineering, Seoul National University, Seoul, Korea', 'School of information and Control, Nanjing University of Information Science and Technology, Nanjing, China'], 'affiliations': [{'raw_affiliation_string': 'School of information and Control, Nanjing University of Information Science and Technology, Nanjing, China', 'institution_ids': ['https://openalex.org/I200845125']}, {'raw_affiliation_string': 'Department of Electrical and Computer Engineering, Seoul National University, Seoul, Korea', 'institution_ids': ['https://openalex.org/I139264467']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5076075267', 'display_name': 'Byonghyo Shim', 'orcid': 'https://orcid.org/0000-0001-5051-1763'}, 'institutions': [{'id': 'https://openalex.org/I4210164379', 'display_name': 'Seoul Media Institute of Technology', 'ror': 'https://ror.org/04ywg4h07', 'country_code': 'KR', 'type': 'education', 'lineage': ['https://openalex.org/I4210164379']}, {'id': 'https://openalex.org/I139264467', 'display_name': 'Seoul National University', 'ror': 'https://ror.org/04h9pn542', 'country_code': 'KR', 'type': 'education', 'lineage': ['https://openalex.org/I139264467']}], 'countries': ['KR'], 'is_corresponding': False, 'raw_author_name': 'Byonghyo Shim', 'raw_affiliation_strings': ['Institute of New Media and Communications and School of Electrical and Computer Engineering, Seoul National University, Seoul, Korea'], 'affiliations': [{'raw_affiliation_string': 'Institute of New Media and Communications and School of Electrical and Computer Engineering, Seoul National University, Seoul, Korea', 'institution_ids': ['https://openalex.org/I4210164379', 'https://openalex.org/I139264467']}]}], 'institution_assertions': [], 'countries_distinct_count': 2, 'institutions_distinct_count': 3, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 5.473, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 51, 'citation_normalized_percentile': {'value': 0.999931, 'is_in_top_1_percent': True, 'is_in_top_10_percent': True}, 'cited_by_percentile_year': {'min': 96, 'max': 97}, 'biblio': {'volume': '64', 'issue': '16', 'first_page': '4194', 'last_page': '4202'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10500', 'display_name': 'Sparse and Compressive Sensing Techniques', 'score': 1.0, 'subfield': {'id': 'https://openalex.org/subfields/2206', 'display_name': 'Computational Mechanics'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T10500', 'display_name': 'Sparse and Compressive Sensing Techniques', 'score': 1.0, 'subfield': {'id': 'https://openalex.org/subfields/2206', 'display_name': 'Computational Mechanics'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T11447', 'display_name': 'Blind Source Separation Techniques', 'score': 0.9991, 'subfield': {'id': 'https://openalex.org/subfields/1711', 'display_name': 'Signal Processing'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T11996', 'display_name': 'Random lasers and scattering media', 'score': 0.9984, 'subfield': {'id': 'https://openalex.org/subfields/3102', 'display_name': 'Acoustics and Ultrasonics'}, 'field': {'id': 'https://openalex.org/fields/31', 'display_name': 'Physics and Astronomy'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/restricted-isometry-property', 'display_name': 'Restricted isometry property', 'score': 0.8968831}, {'id': 'https://openalex.org/keywords/basis-pursuit', 'display_name': 'Basis pursuit', 'score': 0.5337067}, {'id': 'https://openalex.org/keywords/matrix', 'display_name': 'Matrix (chemical analysis)', 'score': 0.46492767}, {'id': 'https://openalex.org/keywords/signal-recovery', 'display_name': 'Signal Recovery', 'score': 0.45322523}], 'concepts': [{'id': 'https://openalex.org/C156872377', 'wikidata': 'https://www.wikidata.org/wiki/Q6786281', 'display_name': 'Matching pursuit', 'level': 3, 'score': 0.97721124}, {'id': 'https://openalex.org/C17902559', 'wikidata': 'https://www.wikidata.org/wiki/Q17099734', 'display_name': 'Restricted isometry property', 'level': 3, 'score': 0.8968831}, {'id': 'https://openalex.org/C124851039', 'wikidata': 'https://www.wikidata.org/wiki/Q2665459', 'display_name': 'Compressed sensing', 'level': 2, 'score': 0.79109466}, {'id': 'https://openalex.org/C124066611', 'wikidata': 'https://www.wikidata.org/wiki/Q28684319', 'display_name': 'Sparse approximation', 'level': 2, 'score': 0.6195574}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.6090506}, {'id': 'https://openalex.org/C51823790', 'wikidata': 'https://www.wikidata.org/wiki/Q504353', 'display_name': 'Greedy algorithm', 'level': 2, 'score': 0.5670471}, {'id': 'https://openalex.org/C151201525', 'wikidata': 'https://www.wikidata.org/wiki/Q177239', 'display_name': 'Limit (mathematics)', 'level': 2, 'score': 0.5353734}, {'id': 'https://openalex.org/C99217422', 'wikidata': 'https://www.wikidata.org/wiki/Q4867576', 'display_name': 'Basis pursuit', 'level': 4, 'score': 0.5337067}, {'id': 'https://openalex.org/C56372850', 'wikidata': 'https://www.wikidata.org/wiki/Q1050404', 'display_name': 'Sparse matrix', 'level': 3, 'score': 0.46589482}, {'id': 'https://openalex.org/C106487976', 'wikidata': 'https://www.wikidata.org/wiki/Q685816', 'display_name': 'Matrix (chemical analysis)', 'level': 2, 'score': 0.46492767}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.46140993}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.45437333}, {'id': 'https://openalex.org/C2989281035', 'wikidata': 'https://www.wikidata.org/wiki/Q120811', 'display_name': 'Signal recovery', 'level': 3, 'score': 0.45322523}, {'id': 'https://openalex.org/C189950617', 'wikidata': 'https://www.wikidata.org/wiki/Q937228', 'display_name': 'Property (philosophy)', 'level': 2, 'score': 0.44744498}, {'id': 'https://openalex.org/C163716315', 'wikidata': 'https://www.wikidata.org/wiki/Q901177', 'display_name': 'Gaussian', 'level': 2, 'score': 0.0703437}, {'id': 'https://openalex.org/C134306372', 'wikidata': 'https://www.wikidata.org/wiki/Q7754', 'display_name': 'Mathematical analysis', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C138885662', 'wikidata': 'https://www.wikidata.org/wiki/Q5891', 'display_name': 'Philosophy', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C121332964', 'wikidata': 'https://www.wikidata.org/wiki/Q413', 'display_name': 'Physics', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C192562407', 'wikidata': 'https://www.wikidata.org/wiki/Q228736', 'display_name': 'Materials science', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C111472728', 'wikidata': 'https://www.wikidata.org/wiki/Q9471', 'display_name': 'Epistemology', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C62520636', 'wikidata': 'https://www.wikidata.org/wiki/Q944', 'display_name': 'Quantum mechanics', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C159985019', 'wikidata': 'https://www.wikidata.org/wiki/Q181790', 'display_name': 'Composite material', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/tsp.2016.2568162', 'pdf_url': None, 'source': {'id': 'https://openalex.org/S168680287', 'display_name': 'IEEE Transactions on Signal Processing', 'issn_l': '1053-587X', 'issn': ['1053-587X', '1941-0476'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319808', 'host_organization_name': 'Institute of Electrical and Electronics Engineers', 'host_organization_lineage': ['https://openalex.org/P4310319808'], 'host_organization_lineage_names': ['Institute of Electrical and Electronics Engineers'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [{'funder': 'https://openalex.org/F4320321001', 'funder_display_name': 'National Natural Science Foundation of China', 'award_id': '61532009'}, {'funder': 'https://openalex.org/F4320321605', 'funder_display_name': 'Government of Jiangsu Province', 'award_id': '15KJA520001'}, {'funder': 'https://openalex.org/F4320322030', 'funder_display_name': 'Ministry of Science, ICT and Future Planning', 'award_id': 'B0717-16-0023'}], 'datasets': [], 'versions': [], 'referenced_works_count': 41, 'referenced_works': ['https://openalex.org/W1027701583', 'https://openalex.org/W1557195970', 'https://openalex.org/W1948737560', 'https://openalex.org/W1974198688', 'https://openalex.org/W1977520307', 'https://openalex.org/W1988529089', 'https://openalex.org/W2004526834', 'https://openalex.org/W2017890892', 'https://openalex.org/W2018324106', 'https://openalex.org/W2028878677', 'https://openalex.org/W2029948740', 'https://openalex.org/W2030449718', 'https://openalex.org/W2033585806', 'https://openalex.org/W2057957447', 'https://openalex.org/W2058428247', 'https://openalex.org/W2062887405', 'https://openalex.org/W2065321782', 'https://openalex.org/W2078204800', 'https://openalex.org/W2079094895', 'https://openalex.org/W2091893102', 'https://openalex.org/W2099641086', 'https://openalex.org/W2113924727', 'https://openalex.org/W2116148865', 'https://openalex.org/W2125696447', 'https://openalex.org/W2127271355', 'https://openalex.org/W2128659236', 'https://openalex.org/W2129131372', 'https://openalex.org/W2129638195', 'https://openalex.org/W2134474909', 'https://openalex.org/W2145096794', 'https://openalex.org/W2160979406', 'https://openalex.org/W2207649167', 'https://openalex.org/W2289917018', 'https://openalex.org/W2296616510', 'https://openalex.org/W2949466416', 'https://openalex.org/W2963275613', 'https://openalex.org/W2963740897', 'https://openalex.org/W3098515897', 'https://openalex.org/W316798226', 'https://openalex.org/W4206096658', 'https://openalex.org/W4250955649'], 'related_works': ['https://openalex.org/W4200104579', 'https://openalex.org/W2952072103', 'https://openalex.org/W2762009856', 'https://openalex.org/W2756726240', 'https://openalex.org/W1988451630', 'https://openalex.org/W1906972028', 'https://openalex.org/W1854242841', 'https://openalex.org/W1800580574', 'https://openalex.org/W166234021', 'https://openalex.org/W119997944'], 'abstract_inverted_index': {'Orthogonal': [0], 'matching': [1], 'pursuit': [2], '(OMP)': [3], 'is': [4], 'a': [5, 60], 'greedy': [6], 'algorithm': [7, 32], 'widely': [8], 'used': [9], 'for': [10, 29], 'the': [11, 24, 30, 56, 69, 77, 83], 'recovery': [12, 36, 91], 'of': [13, 26, 37, 72, 86, 92], 'sparse': [14, 38], 'signals': [15, 50, 94], 'from': [16], 'compressed': [17], 'measurements.': [18], 'In': [19], 'this': [20], 'paper,': [21], 'we': [22], 'analyze': [23], 'number': [25], 'iterations': [27, 54], 'required': [28], 'OMP': [31, 44, 87], 'to': [33], 'perform': [34], 'exact': [35, 90], 'signals.': [39], 'Our': [40, 65], 'analysis': [41], 'shows': [42], 'that': [43], 'can': [45], 'accurately': [46], 'recover': [47], 'all': [48], 'K-sparse': [49, 93], 'within': [51], '[2.8': [52], 'K]': [53], 'when': [55], 'measurement': [57], 'matrix': [58], 'satisfies': [59], 'restricted': [61], 'isometry': [62], 'property': [63], '(RIP).': [64], 'result': [66, 71, 81], 'improves': [67], 'upon': [68], 'recent': [70], 'Zhang': [73], 'and': [74, 82], 'also': [75], 'bridges': [76], 'gap': [78], 'between': [79], "Zhang's": [80], 'fundamental': [84], 'limit': [85], 'at': [88], 'which': [89], 'cannot': [95], 'be': [96], 'uniformly': [97], 'guaranteed.': [98]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W1854242841', 'counts_by_year': [{'year': 2024, 'cited_by_count': 1}, {'year': 2023, 'cited_by_count': 2}, {'year': 2022, 'cited_by_count': 5}, {'year': 2021, 'cited_by_count': 6}, {'year': 2020, 'cited_by_count': 12}, {'year': 2019, 'cited_by_count': 5}, {'year': 2018, 'cited_by_count': 11}, {'year': 2017, 'cited_by_count': 4}, {'year': 2016, 'cited_by_count': 4}, {'year': 2015, 'cited_by_count': 1}], 'updated_date': '2025-01-10T17:09:35.879662', 'created_date': '2016-06-24'}
Publication Information

Basic Information

Access and Citation

AI Researcher Chatbot

Primary Location

Authors

Topics

Keywords

Related Works
