# US 9,882,750 B2 · Method for recovering a sparse communication signal from a receive signal > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,882,750 B2 - Document ID: US9882750B2 - Status: Granted - Kind: B2 - Application number: 15/142,731 - Filed: 2016-04-29 - Published: 2016-08-25 - Granted: 2018-01-30 - Earliest claimed: 2013-11-01 - Assignees: Huawei Technologies Co., Ltd. - Applicants: Huawei Technologies Co., Ltd. - Inventors: Lev Borisovich Rapoport; Yanxing Zeng; Jianqiang Shen; Vladimir Iosifovich Ivanov - Web page: https://patentgrep.com/patent/US9882750B2 ## CPC - H04L 25/03987: {Equalisation for sparse channels} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract The patent application relates to a method for recovering a sparse communication signal from a receive signal, the receive signal being a channel output version of the sparse communication signal, the channel comprising channel coefficients being arranged to form a channel matrix, the method comprising determining a support set indicating a set of first indices of non-zero communication signal coefficients from the channel matrix and the receive signal, determining an estimate of the sparse communication signal upon the basis of the support set, the channel matrix and the receive signal, determining second indices of communication signal coefficients which are not indicated by the support set, and determining the sparse communication signal upon the basis of the support set, the estimate of the sparse communication signal, the second indices and the channel matrix. ## Claims ### Claim 1 A method comprising: determining, by a communication device in a communication network, a support set indicating a set of first indices of non-zero communication signal coefficients from a channel matrix and a receive signal, the receive signal being a channel output version of a sparse communication signal, the channel matrix comprising an arrangement of channel coefficients of the channel; determining, by the communication device, an estimate of the sparse communication signal upon the basis of the support set, the channel matrix and the receive signal; determining, by the communication device, second indices of communication signal coefficients which are not indicated by the support set, wherein determining the second indices of communication signal coefficients comprises minimizing a residual of a dual linear programming problem; and recovering, by the communication device, the sparse communication signal upon the basis of the support set, the estimate of the sparse communication signal, the second indices and the channel matrix. ### Claim 2 (depends on 1) The method according to claim 1, further comprising: updating, by the communication device, the support set upon the basis of the second indices of communication signal coefficients. ### Claim 3 (depends on 2) The method according to claim 2, further comprising: determining, by the communication device, a cardinality of the support set or the updated support set, the cardinality indicating a number of elements of the support set or the updated support set. ### Claim 4 (depends on 1) The method according to claim 1, wherein the sparse communication signal comprises communication signal coefficients and the receive signal comprises receive signal coefficients, and wherein the number of communication signal coefficients is greater than the number of receive signal coefficients. ### Claim 5 (depends on 1) The method according to claim 1, wherein determining the support set or determining the estimate of the sparse communication signal is performed by an orthogonal matching pursuit method. ### Claim 6 (depends on 1) The method according to claim 1, wherein the dual linear programming problem is defined by the following equations: −e≦HTz≦e, yTz→min, wherein H denotes the channel matrix, y denotes the receive signal, e denotes an all unit vector, and z denotes a dual variable. ### Claim 7 (depends on 1) The method according to claim 1, wherein the residual is defined by: ΔS*,j+=1+HjTzS* or ΔS*,j−=1−HjTzS* with zS*=−HS*(HS*THS*)−1eS*, eS*=(eS*,1,eS*,2, . . . ,eS*,l*)T, eS*,i=1 if i∈S*+, eS*,i=−1 if i∈S*−, and S*=S*+∪S*−, wherein S* denotes the support set being divided into two subsets according to signs of the entries of the vector xS*=(HS*THS*)−1HS*Ty, S*+ denotes a subset of the support set S* corresponding to the positive entries of xS*, S*− denotes a subset of the support set S* corresponding to the negative entries of xS*, eS* denotes an auxiliary vector, eS*,i denote coefficients of the auxiliary vector eS* with index i, HS* denotes a channel matrix comprising columns indicated by the support set S*, zS* denotes an estimate solution of a dual linear programming problem, Hj denotes a channel matrix comprising a column indicated by index j, and ΔS*,j + or ΔS*,j− denote the residual. ### Claim 8 (depends on 1) The method according to claim 1, wherein the second indices of communication signal coefficients are determined according to the following equations: j ( 1 ) = argmin j ⁢ Δ S * , j + ⁢ ⁢ or ⁢ ⁢ j ( 1 ) = argmin j ⁢ Δ S * , j - , wherein ΔS*,j+ or ΔS*,j− denote a residual of a dual linear programming problem, and j(1) denotes the second indices of communication signal coefficients. ### Claim 9 (depends on 1) The method according to claim 1, wherein recovering the sparse communication signal is performed according to the following equation: xS(1)=xS*−α(HS*THS*)−1HS*THj(1), α>0 wherein HS* denotes a channel matrix comprising columns indicated by the support set S*, Hj(1) denotes a channel matrix comprising columns indicated by second indices of communication signal coefficients j(1), α denotes a predetermined value, xS* denotes an estimate of the sparse communication signal, and xS(1) denotes the sparse communication signal. ### Claim 10 (depends on 2) The method according to claim 2, wherein updating the support set is performed according to the following equation: S(1)=S*∪{j(1)}\{ji(1)}, wherein j(1) denotes second indices of communication signal coefficients, ji(1) denotes indices of communication signal coefficients to be removed from the support set, i(1) denotes a number of an entry to be removed from the support set, S* denotes the support set, and S(1) denotes the updated support set. ### Claim 11 (depends on 3) The method according to claim 3, wherein determining the support set, determining the estimate of the sparse communication signal, determining the second indices of communication signal coefficients, recovering the sparse communication signal, updating the support set, and determining the cardinality are successively repeated until a stopping criterion is met. ### Claim 12 (depends on 11) The method according to claim 11, wherein the sparse communication signal corresponding to the support set with least cardinality is provided as a recovered sparse communication signal. ### Claim 13 (depends on 11) The method according to claim 11, wherein the stopping criterion is a positive value or a zero value of all residuals of a dual linear programming problem, and wherein a residual is defined by: ΔS*,j+=1+HjTzS* or ΔS*,j−=1−HjTzS* with zS*=−HS*(HS*THS*)−1eS*, eS*=(eS*,1,eS*,2, . . . ,eS*,l*)T, eS*,i=1 if i∈S*+, eS*,i=−1 if i∈S*−, and S*=S*+∪S*−, wherein S* denotes the support set being divided into two subsets according to signs of the entries of the vector xS*=(HS*THS*)−1HS*Ty, S*+ denotes a subset of the support set S* corresponding to the positive entries of xS*, S*− denotes a subset of the support set S* corresponding to the negative entries of xS*, eS* denotes an auxiliary vector, eS*,i denote coefficients of the auxiliary vector eS* with index i, HS* denotes a channel matrix comprising columns indicated by the support set S*, zS* denotes an estimate solution of a dual linear programming problem, Hj denotes a channel matrix comprising a column indicated by index j, and ΔS*,j + or ΔS*,j − denote the residual. ### Claim 14 (depends on 11) The method according to claim 11, wherein the stopping criterion is an expiry of a length of a predetermined time interval. ### Claim 15 (depends on 2) The method according to claim 2, further comprising: determining a cardinality of the support set or the updated support set, the cardinality indicating a number of elements of the support set or the updated support set. ### Claim 16 (depends on 2) The method according to claim 2, wherein the sparse communication signal comprises communication signal coefficients and the receive signal comprises receive signal coefficients, and wherein the number of communication signal coefficients is greater than the number of receive signal coefficients. ### Claim 17 (depends on 2) The method according to claim 2, wherein the dual linear programming problem is defined by the following equations: −e≦HTz≦e, yTz→min, wherein H denotes the channel matrix, y denotes the receive signal, e denotes an all unit vector, and z denotes a dual variable. ### Claim 18 (depends on 1) The method according to claim 1, wherein the residual is defined by: ΔS*,j+=1+HjTzS* or ΔS*,j−=1−HjTzS* with zS*=−HS*(HS*THS*)−1eS*, eS*=(eS*,1,eS*,2, . . . ,eS*,1*)T, eS*,i=1 if i∈S*+, eS*,i=−1 if i∈S*−, and S*=S*+∪S*−, wherein S* denotes the support set being divided into two subsets according to signs of the entries of the vector xS*=(HS*THS*)−1HS*Ty, S*+ denotes a subset of the support set S* corresponding to the positive entries of xS*, S*− denotes a subset of the support set S* corresponding to the negative entries of xS*, eS* denotes an auxiliary vector, eS*,i denote coefficients of the auxiliary vector eS* with index i, HS* denotes a channel matrix comprising columns indicated by the support set S*, zS* denotes an estimate solution of a dual linear programming problem, Hj denotes a channel matrix comprising a column indicated by index j, and ΔS*,j + or ΔS*,j − denote the residual. ### Claim 19 (depends on 2) The method according to claim 2, wherein the second indices of communication signal coefficients are determined according to the following equations: j ( 1 ) = argmin j ⁢ Δ S * , j + ⁢ ⁢ or ⁢ ⁢ j ( 1 ) = argmin j ⁢ Δ S * , j - , wherein ΔS*,j + or ΔS*,j − denote a residual of a dual linear programming problem, and j(1) denotes the second indices of communication signal coefficients. ### Claim 20 (depends on 2) The method according to claim 2, wherein recovering the sparse communication signal is performed according to the following equation: xS(1)=xS*−α(HS*THS*)−1HS*THj(1), α>0 wherein HS* denotes a channel matrix comprising columns indicated by the support set S*, Hj(1) denotes a channel matrix comprising columns indicated by second indices of communication signal coefficients j(1), α denotes a predetermined value, xS* denotes an estimate of the sparse communication signal, and xS(1) denotes the sparse communication signal. ### Claim 21 A non-transitory computer readable medium containing instructions that, when executed by at least one processor of a communication device in a communication network, cause the at least one processor to: determine a support set indicating a set of first indices of non-zero communication signal coefficients from a channel matrix and a receive signal, the receive signal being a channel output version of a sparse communication signal, the channel matrix comprising an arrangement of channel coefficients of the channel; determine an estimate of the sparse communication signal upon the basis of the support set, the channel matrix and the receive signal; determine second indices of communication signal coefficients which are not indicated by the support set, wherein determining the second indices of communication signal coefficients comprises minimizing a residual of a dual linear programming problem; and recover the sparse communication signal upon the basis of the support set, the estimate of the sparse communication signal, the second indices and the channel matrix.