Provided are a program, a method, and an apparatus for decoding coded data, capable of completely restoring an original stream when decoded data is coded again by causing a computer to function as: means for receiving an input of a signal coded by lossy compression and orthogonally projecting an optional real number vector on one convex aggregate X in a first vector space in which the decoded signal is present; means for judging convergence of convex projection and obtaining a real number vector x belonging to the aggregate X to output the same as a decoded signal when the convergence of the convex projection is judged; and means for orthogonally projecting an optional vector of the first vector space on one convex aggregate Y in a second vector space different from the first vector space when the convergence of the convex projection is not judged, and then repeating orthogonal projection on the aggregate X and the aggregate Y with the coded signal set as an initial value.